题目描述：神犇YY虐完数论后给傻×kAc出了一题
给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对
kAc这种傻×必然不会了，于是向你来请教……
多组输入（大概也就一万组吧……）
解决本题需要了解莫比乌斯反演的知识，所以先来普及知识点（最为枯燥的部分，但忍下去）。
莫比乌斯函数
：莫比乌斯函数是啥啊？
：（莫比乌斯是一个由容斥系数所构成的函数）。
- μ（d）的定义：
- 当d=1时，μ（d）=1；
- 当d=\(\Pi_{i=1}^kp_i\)且\(p_i\)为互质素数时，μ（d）=\((-1)^k\)。(说直白点，就是d分解质因数后，没有幂次大于平方的质因子，此时函数值根据分解的个数决定)；
- 只要当d含有任何质因子的幂大于等于2，则函数值为0。
- 莫比乌斯函数的一些其他有趣的性质：
- 对于任意正整数n，\(\sum_{d|n}μ(d)\)=[n=1]。(PS:这一条性质是莫比乌斯反演中最常用的)
- 对于任意正整数n，\(\sum_{d|n} \frac{μ(d)}{d}\)=\(\frac{φ(n)}{n}\)。（这个性质很奇妙，把欧拉函数与莫比乌斯函数结合起来，下次学杜教筛会证明）。
求莫比乌斯函数的程序实现不难，只需要在线性筛的程序上略作修改，便可以筛出μ函数。
void mu_get(){
mu[1]=1;
for(int i=2;i<=n;++i){
if(!v[i]){
p[++m]=i,mu[i]=-1;
}
for(int j=1;j<=m;++j){
if(p[j]>v[i]||i*p[j]>n) break;
v[i*p[j]]=p[j];
if(i%p[j]) break;
else mu[i*p[j]]=-mu[i];
}
}
}莫比乌斯反演
解决了莫比乌斯函数的问题后，我们就迎来了恶心的莫比乌斯反演。
莫比乌斯反演定理：F（n）和f（n）是定义在非负整数集合上的两个函数，并且满足条件：
\[F(n)=\sum_{d|n}f(d)\]
那么现在存在一个结论：
\[f(n)=\sum_{d|n}μ(d)F(\frac{n}{d})\]
莫比乌斯反演的证明主要有两种方式，其中一种就是通过定义来证明；另一种利用狄利克雷卷积。先来说一说第一种证明方法：
\[\sum_{d|n}μ(d)F(\frac{n}{d})=\sum_{d|n}μ(d)\sum_{i|\frac{n}{d}}f(i)\]
\[=\sum_{i|n}f(i)\sum_{d|\frac{n}{i}}μ(d)=f(n)\]
(PS:如果不知道第二部如何推导第三部，可以考虑第二个式子枚举的i与d的关系，发现可以调换一下枚举的方式。如果不知道最后一步怎么来的，可以去看一下上面莫比乌斯函数的性质1)。
当然，莫比乌斯反演有另外的一种形式，当F（n）和f（n）满足：
\[F(n)=\sum_{n|d}f(d)\]
可以推出：
\[f(n)=\sum_{n|d}μ(\frac{d}{n})F(d)\]
感觉这个式子，可能在莫比乌斯反演中更加好用。
回到本题
显然，Ans=\(\sum_{p\epsilon prim}\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=p]\)
对于这种和gcd有关的莫比乌斯反演，我们一般另f（d）为gcd（i，j）=d的个数，即f(d)=\(\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d]\) 。那么F（n）为gcd（i，j）为n或者n的倍数的个数，即：
\[F(n)=\sum_{n|d}f(d)=\lfloor\frac{N}{n}\rfloor\lfloor\frac{M}{m}\rfloor\]
那么根据莫比乌斯反演定理：
\[f(n)=\sum_{n|d}μ(\frac{d}{n})F(d)\]
接下来就是化简式子了！
\[Ans=\sum_{p\epsilon prim}f(p)\]
\[=\sum_{p\epsilon prim}\sum_{p|d}μ(\frac{d}{p})F(d)\]
换一个枚举项，枚举\(\lfloor\frac{d}{p}\rfloor\)
\[\sum_{p\epsilon prim}\sum_{d=1}^{min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}μ(d)F(dp)=\sum_{p\epsilon prim}\sum_{d=1}^{min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}μ(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor\]
这个dp看着很不爽，我们把它换成T
\[Ans=\sum_{T=1}^{min(n,m)}\sum_{t|T,t\epsilon prim}μ(\frac{T}{t})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\]
\[Ans=\sum_{T=1}^{min(n,m)}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{t|T,t\epsilon prim}μ(\frac{T}{t})\]
这样就已经可以O（n）求了。不过这道题有多组数据，所以直接O（n）求会挂。所以我们利用前缀和的思路，打一个整除分块，就可以O（n）预处理，O（\(\sqrt{n}\)）求每一组数据了。
历经磨难终于A掉了这道题，哎数学题推式子我总是看着题解一遍一遍推，还是没有感觉，弱啊……
Coding
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e7+10;
int n,m,cnt,p[N],v[N],mu[N];ll sum[N],ans,g[N];
void get_mu(int a){
mu[1]=1;
for(int i=2;i<=a;++i){
if(!v[i]){
p[++cnt]=i;mu[i]=-1;
}
for(int j=1;j<=cnt;++j){
if(p[j]*i>a) break;
v[i*p[j]]=p[j];
if(i%p[j]==0) break;
else mu[i*p[j]]=-mu[i];
}
}
for(int i=1;i<=cnt;++i){
for(int j=1;j*p[i]<=a;++j) g[p[i]*j]+=mu[j];
}
for(int i=1;i<=a;++i) sum[i]=sum[i-1]+g[i];
}
int main(){
get_mu(1e7);
int t;scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
ans=0;
if(n>m) swap(n,m);
for(int l=1,r;l<=n;l=r+1){
r=min((n/(n/l)),m/(m/l));
ans+=(sum[r]-sum[l-1])*(n/l)*(m/l);
}
printf("%lld\n",ans);
}
return 0;
}