#include #include using namespace std; typedef long long LL; const int N = 1 << 24, M = 1010; int m, n, mul_x, add_x, mul_y, add_y, MOD, x[M]; int last_x, last_y, last_a, last_b; // 四个递推序列的当前项 LL z[N]; // 先存各评级数量,随后原地改为对应评级的正倍数和 /** * 问题:给定各评级的带权出现次数,对每组 $(a,b)$ 求评级是 $a$ 的倍数、 * 但不是 $ab$ 的倍数的总权值;数据与询问的后缀由递推式生成。 * * 线索: * - $N\le 10^7$,不能保存四个长度为 $N$ 的生成序列。 * - $MOD\le 2^{24}$,一个长度为 $MOD$ 的 64 位数组约占 128 MB。 * - 每次询问只关心某两个数的所有倍数,可以统一预处理倍数和。 * * 思维链: * 1. 生成式只依赖前一项,因此流式生成 $(x_i,y_i)$,直接累加到 $z[x_i]$。 * 2. 定义 $S(d)=\sum_{k\ge 1,\,kd