首页 > 代码库 > bzoj 2005
bzoj 2005
裸的2D gcd。ans=(Σ(d<=n)phi[d]*(n/d)*(m/d))*2-n*m;
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,phi[100005]; 9 void shai() 10 { 11 phi[1]=1; 12 for(int i=2;i<=100000;i++) 13 { 14 if(!phi[i])su[++cnt]=i,pr[i]=i,phi[i]=i-1; 15 for(int j=1;su[j]<=pr[i]&&su[j]*i<=100000&&j<=cnt;j++) 16 { 17 pr[su[j]*i]=su[j]; 18 if(su[j]==pr[i])phi[su[j]*i]=phi[i]*su[j]; 19 else phi[su[j]*i]=phi[i]*(su[j]-1); 20 } 21 } 22 } 23 signed main() 24 { 25 shai(); 26 scanf("%lld%lld",&n,&m);int ans=0; 27 for(int i=1;i<=min(n,m);i++)ans+=phi[i]*(n/i)*(m/i); 28 ans*=2;ans-=(n*m); 29 printf("%lld\n",ans); 30 return 0; 31 }
bzoj 2005
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。