首页 > 代码库 > bzoj 1101 zap
bzoj 1101 zap
gcd(x,y)=d-->gcd(x/d,y/d)=1。
即求Σ(i<=n/d)Σ(j<=m/d) e(gcd(i,j))
因为e=miu×1,可以卷积。
因为多组询问,需要sqrt(n)计算。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define int long long 6 using namespace std; 7 int n,m; 8 int pr[100005],su[100005],cnt,miu[100005]; 9 int sum[100005]; 10 void shai() 11 { 12 miu[1]=1; 13 for(int i=2;i<=50000;i++) 14 { 15 if(!pr[i])su[++cnt]=i,pr[i]=i,miu[i]=-1; 16 for(int j=1;su[j]<=pr[i]&&su[j]*i<=100000&&j<=cnt;j++) 17 { 18 pr[su[j]*i]=su[j]; 19 if(su[j]==pr[i])miu[su[j]*i]=0; 20 else miu[su[j]*i]=miu[i]*(-1); 21 } 22 } 23 for(int i=1;i<=50000;i++)sum[i]=sum[i-1]+miu[i]; 24 return ; 25 } 26 signed main() 27 { 28 shai(); 29 int cas; 30 scanf("%lld\n",&cas); 31 while(cas--) 32 { 33 int ans=0; 34 int n,m;int d; 35 scanf("%lld%lld%lld",&n,&m,&d); 36 n/=d;m/=d;if(n>m)swap(n,m); 37 int r; 38 for(int i=1;i<=n;i=r+1) 39 { 40 int y=n/i;int x=m/i;r=min(n/y,m/x); 41 ans+=(sum[r]-sum[i-1])*(x*y); 42 } 43 printf("%lld\n",ans); 44 } 45 return 0; 46 }
bzoj 1101 zap
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。