2820: YY的GCDTime Limit:10 SecMemory Limit:512 MBSubmit:807Solved:404[Submit][Status]Description
神犇YY虐完数论后给傻×kAc出了一题
给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对
多组输入
Input
第一行一个整数T 表述数据组数
接下来T行，每行两个正整数，表示N, M
Output
T行，每行一个整数表示第i组数据的结果
Sample Input
210 10100 100
Sample Output
302791
HINT
T = 10000N, M <= 10000000
莫比乌斯函数。
iwtwiioi的题解非常详细orz
大概说一下做法，求gcd(x,y)=k的(x,y)的对数就是【BZOJ 1101】，那么这道题可以枚举k来求，但是会TLE，那么我们考虑公式的变形。（详见iwtwiioi的题解。。）
接下来的关键就是求g[x]函数：根据线性筛的原理，为了方便，把g[x]变成求g[kp]。
k是线性筛的时候当前要处理的数，p是枚举已经筛出来的质数(一定<k)。
就像求莫比乌斯函数一样，分三种情况：
1.k为质数，g[k]=1
2.k%p=0，说明p的指数>=2，然后根据g[x]函数的计算方法来计算此时的g[kp]，分p’=p和p’!=p两种情况。
得出g[kp]=mu[k]
3.k%p!=0，，说明p的指数=1，然后根据g[x]函数的计算方法来计算此时的g[kp]，分p’=p和p’!=p两种情况。
得出g[kp]=-g[k]
于是在求莫比乌斯函数的同时就把g数组求好了，按照原来的分块方法计算即可~
#include <iostream>#include <cmath>#include <algorithm>#include <cstdio>#include <cstdlib>#include <cstring>#define LL long long#define M 10000005using namespace std;int check[M],mu[M],p[M],sum[M],g[M];void Getmobius(){mu[1]=1;int tot=0;for (int i=2;i<=M;i++){if (!check[i]){p[++tot]=i;mu[i]=-1;g[i]=1;}for (int j=1;j<=tot;j++){if (p[j]*i>M) break;check[p[j]*i]=1;if (i%p[j]==0){mu[p[j]*i]=0;g[p[j]*i]=mu[i];break;}mu[p[j]*i]=-mu[i];g[p[j]*i]=mu[i]-g[i];}}for (int i=1;i<=M;i++)sum[i]=sum[i-1]+g[i];}LL Calc(int a,int b){LL ans=0LL;int pos;for (int d=1;d<=min(a,b);d=pos+1){pos=min(a/(a/d),b/(b/d));ans+=(LL)(sum[pos]-sum[d-1])*(a/d)*(b/d);}return ans;}int main(){Getmobius();int T;scanf("%d",&T);while (T–){int n,m;scanf("%d%d",&n,&m);printf("%lld\n",Calc(n,m));}return 0;}
感悟：
1.发现普通的计算方法TLE，对式子变形化简
2.求g数组套在线性筛中~
勇士面前无险路。
