Description:


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

Input:


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

Output:


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

Sample Input:


Sample Output:


HINT:


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

题解:


SDOI的数学题就是强。
我们把题意转换一下,就是需要求:

\[ \sum_{i=1}^n\sum_{j=1}^m[\sigma (gcd(i, j)) \le a] \sigma (gcd(i, j))\]

其中 \(\sigma (n)\) 表示n的约数和。
先不考虑a的限制,然后我们开始转换:(不妨设 \(n\le m\) )

\[ \begin{align} \sum_{i=1}^n\sum_{j=1}^m \sigma (gcd(i, j)) & = \sum_{i=1}^n\sum_{j=1}^m\sum_{g|i, g|j} [gcd(i, j)=g] \sigma (g) \\ & = \sum_{g=1}^n\sigma (g)\sum_{i=1}^{\lfloor\frac{n}{g}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{g}\rfloor}[gcd(i, j)=1]\\ & = \sum_{g=1}^n\sigma (g)\sum_{i=1}^{\lfloor\frac{n}{g}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{g}\rfloor}\sum_{d|i, d|j} \mu (d)\\ & = \sum_{g=1}^n\sigma (g)\sum_{d=1}^{\lfloor\frac{n}{g}\rfloor} \mu (d) \lfloor\frac{n}{dg}\rfloor \lfloor\frac{m}{dg}\rfloor\\ & = \sum_{g=1}^n \lfloor\frac{n}{g}\rfloor \lfloor\frac{m}{g}\rfloor \sum_{d|g} \sigma (d) \mu (\frac{g}{d}) \end{align}\]

\[ h(n)=\sum_{d|n} \sigma (d) \mu (\frac{n}{d})\]

现在就是要求

\[ \sum_{g=1}^n \lfloor\frac{n}{g}\rfloor \lfloor\frac{m}{g}\rfloor h(g)\]

其中 \(h(i)\) 可以用 \(O(n\ln n)\) 的时间预处理,然后原式可以用 \(O(\sqrt n)\) 的时间计算.

现在我们考虑a的限制.

\[ \sum_{g=1}^n \lfloor\frac{n}{g}\rfloor \lfloor\frac{m}{g}\rfloor [\sigma (d) \le a] \sum_{d|g} \sigma (d) \mu (\frac{g}{d})\]

如果那些大于a的 \(\sigma (d)\) 在预处理时没有去更新 \(h(g)\) 就可以了.
我们把询问按照a排序,然后按照 \(\sigma (i)\) 的大小从小到大去更新 \(h(i)\) ,每当达到一个a的上界时停止更新,并分块计算一遍答案.
这样我们把 \(h(i)\) 用树状数组维护就可以了.
时间复杂度 \(O(n\ln n \log_2 n + q\sqrt n \log_2 n)\)