题目描述

FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。

输入格式

第一行包含一个正整数n，表示一共有n组询问。（1<=n<= 50000）接下来n行，每行表示一个询问，每行三个正整数，分别为a,b,d。（1<=d<=a,b<=50000）

输出格式

对于每组询问，输出一个正整数，表示满足条件的整数对数。

题目解析

无限膜拜莫比乌斯反演和分块。

首先对题目条件做一个变换。令$a' = a/k,b' = b/k$，则根据最大公约数的性质，有

$$\sum\limits_{i = 1}^a {\sum\limits_{j = 1}^b {[\gcd (i,j) = = k]} } \Leftrightarrow \sum\limits_{i = 1}^{a'} {\sum\limits_{j = 1}^{b'} {[\gcd (i,j) = = 1]} }$$

观察上式，既有i,j互质，那么我们可以作进一步推导：

$$\begin{aligned} \sum\limits_{i = 1}^{a'} {\sum\limits_{j = 1}^{b'} {[\gcd (i,j) = = 1]} } & = \sum\limits_{i = 1}^{a'} {\sum\limits_{j = 1}^{b'} {\sum\limits_{d{\kern 1pt} |{\kern 1pt} \gcd (i,j)} {\mu (d)} } } \\ & = \sum\limits_{i = 1}^{a'} {\sum\limits_{j = 1}^{b'} {\sum\limits_{d{\kern 1pt} |{\kern 1pt} i\& \& d{\kern 1pt} |{\kern 1pt} j} {\mu (d)} } } \\ & = \sum\limits_{d = 1}^{\min \{ a',b'\} } {\mu (d)\left\lfloor {\frac{{a'}}{d}} \right\rfloor } \left\lfloor {\frac{{b'}}{d}} \right\rfloor \end{aligned}$$

推导至(1)式使用了莫比乌斯函数的性质，(2)式运用乘法原理，变换求和指标，得到(3)式。至此，我们所求的结果可以用线性时间求出。

但是询问有50000个，这样做还是超时，考虑优化。注意到${\left\lfloor {\frac{{a'}}{d}} \right\rfloor }$的取值最多只有$2\sqrt a'$个，${\left\lfloor {\frac{{b'}}{d}} \right\rfloor }$同理。于是可以分块，把取值相同的一段合并一起算。用$O(n)$预处理莫比乌斯函数及其前缀和，一次询问只需$O(\sqrt n )$时间，至此问题成功解决。

利用本题的思想，还可以解决类似的2301，此处不再展开。