Description
FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。
Input
第一行包含一个正整数n，表示一共有n组询问。（1<=n<= 50000）接下来n行，每行表示一个询问，每行三个正整数，分别为a,b,d。（1<=d<=a,b<=50000）
Output
对于每组询问，输出到输出文件zap.out一个正整数，表示满足条件的整数对数。
Sample Input
24 5 26 4 3
Sample Output
32
Solution
\[ \begin{align} ans=&\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[\gcd(i,j)=1]\\ =&\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sum_{d|i\&d|j}\mu(d)\\ =&\sum_{t=1}^{min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(t)\lfloor\frac{n}{dt}\rfloor\lfloor\frac{m}{dt}\rfloor \end{align} \]
预处理\(\mu\)前缀和就好了。复杂度\(O(n+T\sqrt{n})\)。
#includeusing namespace std;#define ONLINE_JUDGE#ifdef ONLINE_JUDGE#define getchar() ((p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin)),p1==p2)?EOF:*p1++)#endifnamespace fast_IO { char buf[1<<21],*p1=buf,*p2=buf; template inline void read(T &x) { x=0;T f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } template inline void read(T& x,Args& ...args) { read(x),read(args...); } char buf2[1<<21],a[80];int p,p3=-1; inline void flush() {fwrite(buf2,1,p3+1,stdout),p3=-1;} template inline void write(T x) { if(p3>(1<<20)) flush(); if(x<0) buf2[++p3]='-',x=-x; do {a[++p]=x%10+48;} while(x/=10); do {buf2[++p3]=a[p];} while(--p); buf2[++p3]='\n'; } template inline void write(T x,Args ...args) { write(x),write(args...); }}using fast_IO :: read;using fast_IO :: write;using fast_IO :: flush;const int maxn = 5e4+10;int pri[maxn],tot,mu[maxn],vis[maxn];void sieve() { mu[1]=1; for(int i=2;i