Bzoj 2820: YY的GCD(莫比乌斯反演+除法分块)

本文主要是介绍Bzoj 2820: YY的GCD(莫比乌斯反演+除法分块)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2820: YY的GCD
Time Limit: 10 Sec Memory Limit: 512 MB
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

大佬的题解还是弱啊orz

/*
莫比乌斯.
最后用除法分块..
筛莫比乌斯函数部分:
显然每个素数直接计算mu[i]=-1.
我们知道莫比乌斯函数值是(-1)^k,k是互异质数的个数.
对于一个合数x,令它质因子的最小的那个为p1,
则有x=p1*t1,另设一个与异于p1的质因子为p2.
则有p1*t1=p2*t2.
因为p1与p2互素,所以p2|t1,p1|t2.
所以当i枚举到t2时,因为p1|t2,所以退出
**有一个疑问:就是如果有一个数x1>x,那直接退出以后是不是会影响x1函数值的计算???数学不好没证出来orz**
假如有一个x1=t1*p,且p是x1最大的质因数.
当i枚举到t1时,计算一下x的函数值.
所以我们保证算的每一个合数的莫比乌斯函数的时候
都是在最后一个计算素数的时候的
即每个函数值都只计算了一次.
复杂度是O(n)哒.
*/
#include<iostream>
#include<cstdio>
#define MAXN 10000001
#define LL long long
using namespace std;
int mu[MAXN],pri[MAXN],tot,g[MAXN],sum[MAXN],last;
LL ans,n,m;
bool vis[MAXN];
void pre()
{mu[1]=1;for(int i=2;i<=MAXN-1;i++){if(!vis[i]) pri[++tot]=i,mu[i]=-1,g[i]=1;for(int j=1;j<=tot&&i*pri[j]<=MAXN-1;j++){vis[i*pri[j]]=true;if(i%pri[j]) mu[i*pri[j]]=-mu[i],g[i*pri[j]]=mu[i]-g[i];else {mu[i*pri[j]]=0;g[i*pri[j]]=mu[i];break;}}}for(int i=1;i<=MAXN-1;i++) sum[i]=sum[i-1]+g[i];}
int main()
{int t,x,y;pre();scanf("%d",&t);while(t--){scanf("%lld%lld",&n,&m);if(n>m) swap(n,m);ans=0;for(LL i=1;i<=n;i=last+1){last=min(n/(n/i),m/(m/i));ans+=(n/i)*(m/i)*(sum[last]-sum[i-1]);}printf("%lld\n",ans);}return 0;
}