3
21
2016
0

[BZOJ2820] YY的GCD

第二道莫比乌斯反演!

这题和HAOI2011的Problem b很像,但是改成了质数……

懒得写题解了:传送门

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int mu[10000005],g[10000005],T,n,m,pri[1000005],cnt,tab[10000005];

void Pre(int n){
mu[1]=1;
for(int i=2;i<=n;i++){
	if(!tab[i]){g[i]=1;mu[i]=-1;pri[++cnt]=i;}
	for(int j=1;j<=cnt && pri[j]*i<=n;j++){
		tab[i*pri[j]]=1;
		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<=n;i++)tab[i]=tab[i-1]+g[i];
}

long long Solve(long long n,long long m){
if(n>m)swap(n,m);
long long ans=0;
for(int i=1,last;i<=n;i=last+1){
	last=min(n/(n/i),m/(m/i));
	ans+=(n/i)*(m/i)*(tab[last]-tab[i-1]);
}
return ans;
}

int main(){
freopen("2820.in","r",stdin);
freopen("2820.out","w",stdout);
Pre(10000000);
scanf("%d",&T);
while(T--){
	scanf("%d %d",&n,&m);
	printf("%lld\n",Solve(n,m));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 413

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com