【bzoj2820】【YY的gcd】【莫比乌斯反演】

本文主要是介绍【bzoj2820】【YY的gcd】【莫比乌斯反演】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
神犇YY虐完数论后给傻×kAc出了一题
给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对
kAc这种傻×必然不会了，于是向你来请教……
多组输入
Input
第一行一个整数T 表述数据组数
接下来T行，每行两个正整数，表示N, M
Output
T行，每行一个整数表示第i组数据的结果
Sample Input
2
10 10
100 100
Sample Output
30
2791
HINT
T = 10000
N, M <= 10000000
题解：
设p为质数,暴力搞的话显然是

\sum p \sum d = 1 ⌊ n p ⌋ ⌊ n p d ⌋ ⌊ m p d ⌋ u (d)

$\sum_{p}^{}\sum_{d=1}^{\lfloor \frac{n}{p} \rfloor}\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor u(d)$
设T=pd,稍微化一下可以变成

\sum T = 1 n ⌊ n T ⌋ ⌊ m T ⌋ \sum p | T u (T p)

$\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{p|T}^{}u(\frac{T}{p})$
设g[t]=

∑p|Tu(Tp) $\sum_{p|T}^{}u(\frac{T}{p})$
考虑只要求出g数组就可以

n√ $\sqrt n$ 处理询问了。
g数组可以枚举每个质数然后更新它的倍数.
可以证明这样处理是O(n)的。

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 10000010
using namespace std;
int u[N],p[N],n,m,t,pos;
long long g[N],ans;
bool f[N];
void pre(){u[1]=1;for (int i=2;i<=N-10;i++){if (!f[i]){p[++p[0]]=i;u[i]=-1;}for (int j=1;j<=p[0]&&i*p[j]<=N-10;j++){f[i*p[j]]=1;if (i%p[j]==0){u[i*p[j]]=0;break;}u[i*p[j]]=-u[i];}}for (int i=1;i<=p[0];i++)for (int j=1;j<=(N-10)/p[i];j++)g[p[i]*j]+=(long long)u[j];for (int i=1;i<=N-10;i++) g[i]+=g[i-1];
}
int main(){ scanf("%d",&t);pre();while (t--){scanf("%d%d",&n,&m);ans=0;if (n>m) swap(n,m);for (int i=1;i<=n;i=pos+1){pos=min(n/(n/i),m/(m/i));ans+=(long long)(n/i)*(long long)(m/i)*(g[pos]-g[i-1]); }printf("%lld\n",ans);}
}