神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种
傻×必然不会了，于是向你来请教……多组输入
T = 10000
N, M <= 10000000
我们很容易就可以得出一下这个复杂度爆炸的式子：
$\sum_ {prime(p)}^{n} \sum_ {d=1}^{n/p} μ(d) \left\lfloor \frac{n}{pd} \right\rfloor \left\lfloor \frac{m}{pd} \right\rfloor$
但是有10000个case，这个复杂度明显爆炸...我们设$k=pd$
可以得到一下式子：
$\sum_ {k=1}^{n} \left\lfloor \frac{n}{k} \right\rfloor \left\lfloor \frac{m}{k} \right\rfloor \sum_ {prime(p) p\mid k} μ(\frac {k}{p})$
然后对于后面的μ我们可以预处理前缀和，这样单个case复杂度大概可以降到$sqrt(n)+sqrt(m)$...
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
#define int long long
using namespace std;
const int maxn=10000000+5;
int n,m,cas,cnt,f[maxn],mu[maxn],pri[maxn],vis[maxn];
inline void prework(void){
mu[1]=1;
for(int i=2;i<=10000000;i++){
if(!vis[i])
pri[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*pri[j]<=10000000;j++){
vis[i*pri[j]]=1;
if(i%pri[j]==0){
mu[i*pri[j]]=0;
break;
}
mu[i*pri[j]]=-mu[i];
}
}
for(int i=1;i<=cnt;i++)
for(int j=1;pri[i]*j<=10000000;j++)
f[pri[i]*j]+=mu[j];
for(int i=1;i<=10000000;i++)
f[i]+=f[i-1];
}
signed main(void){
scanf("%lld",&cas);prework();
while(cas--){
scanf("%lld%lld",&n,&m);
if(n>m)
swap(n,m);
int ans=0,r;
for(int i=1;i<=n;i=r+1){
r=min(n/(n/i),m/(m/i));
ans+=(f[r]-f[i-1])*(n/i)*(m/i);
}
printf("%lld\n",ans);
}
return 0;
}
By NeighThorn
原文：http://www.cnblogs.com/neighthorn/p/6415260.html