Description

有一张(n×m)的数表，其第i行第j列（(，1 le i leq n，1 le j le m)）的数值为
能同时整除(i)和(j)的所有自然数之和。给定(a)，计算数表中不大于(a)的数之和。

Input

输入包含多组数据。
输入的第一行一个整数(Q)表示测试点内的数据组数，接下来Q行，每行三个整数(，，n，m，a)((|a| < =10^9))描述一组数据。

Output

对每组数据，输出一行一个整数，表示答案模(2^{31})的值。

Sample Input

2
4 4 3
10 10 5

Sample Output

20
148

HINT

(1 le n,m le 10^5 \ 1 le Q le 2×10^4)

Solution

先忽略(a)的条件。

令(f(n))表示(n)的所有约数之和, (sum(x))表示(且x=gcd(i,j),1le i le n且1le j le m)的数对数量.

按照之前的反演，(sum(x)=sumlimits_{x|d}mu(frac dx)lfloorfrac nd floorlfloorfrac md floor=sum)

[egin{aligned} ans&=sum_{i=1}^nsum_{j=1}^msum_{d|i且d|j}d\ &=sum_{i=1}^nsum_{j=1}^mf(gcd(i,j))\ &=sum_{d=1}^{min(n,m)}f(d)sum(d)\ &=sum_{d=1}^{min(n,m)}f(d)sum_{x|d}mu(frac dx)lfloorfrac nd floorlfloorfrac md floor\ &=sum_{d=1}^{min(n,m)}f(d)sum_{k=1}^{lfloor min(n,m)/d floor}mu(frac {kx}x)lfloorfrac n{kx} floorlfloorfrac m{kx} floor\ &=sum_{T=1}^{min(n,m)}lfloorfrac nT floorlfloorfrac mT floorsum_{d|T}f(d)mu(frac Td)\ &=sum_{T=1}^{min(n,m)}lfloorfrac nT floorlfloorfrac mT floor g(T) &令g(x)=sum_{d|x}f(d)mu(frac xd) end{aligned} ]

其实(g(x))是可以暴力求解的...因为(x)的因数个数不是很多。但是我们不能直接算完，因为有(a)的限制。由此要引入树状数组。

回头看(a)的条件，从第三行等式来看，只有(dleq a)的(f(d))才能有贡献。

我们用一个树状数组来维护(g(x))的前缀和，那么对于询问，按照(a)排序，将所有(xle a)的(f(x))，枚举(x|y)的(y)，更新(g(y)+=f(x)mu(frac yx))。

这样按照分块的套路求解(ans)即可.

f函数求解

(f(x)=sumlimits_{d|x}d)

(f(x))是积性函数，可以用线性筛求解：

(1) (x)是质数时，(f(x)=1+x)

(2)循环(i)与(p)筛到(x)， (x)=(p*i).

若(i mid p)，则(i)与(p)互质，那么(f(x)=f(i)f(p)=f(i)*(p+1)).

若(i|p)，记(i)去除所有(p)因子后的数为(a). 则(f(x)=f(i)*p+f(a)).

记(i=p_1^{q_1}p_2^{q_2}...p_k^{q_k})，则(x=p_1^{q_1}p_2^{q_2}...p_{loc}^{q_{loc}+1}...p_k^{q_k})，(a=p_1^{q_1}..p_{loc-1}^{q_{loc-1}}p_{loc+1}^{q_{loc}+1}...p_k^{q_k}).不严谨地，这里(p_{loc})和(q_{loc})分别代表的是(p)，与(p)在质因数分解中的指数。

[egin{aligned} f(i)*p&=(1+p1+...+p1^{q1})...(1+p_{loc}+...+p_{loc}^{q_{loc}})...(1+p_k+...+p_k^{q_k})*p\ &=(p_{loc}+p_{loc}^2+..+p_{loc}^{q_{loc}+1})f(a)\ herefore f(i)*p&+f(a)=(1+p_{loc}+p_{loc}^2+...+p_{loc}^{q_{loc}+1})f(a)=f(x) end{aligned} ]

【BZOJ3529】【SDOI2014】 数表