首页 > 代码库 > UVa10820 Send a Table
UVa10820 Send a Table
只有互质的数对才对答案有贡献。
假设有一个数x，和它互质的数的个数就是它的欧拉函数。
1<=x<=n，所以要求欧拉函数前缀和。
把数对前后两个数颠倒，总答案数为前缀和乘2
(1,1)不能颠倒
所以：求出欧拉函数前缀和，乘2，减1，就是答案。
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=51000; 9 int phi[mxn];10 int sum[mxn];11 void Euler(){12 int i,j;13 phi[1]=1;14 for(i=2;i<mxn;i++)15 if(!phi[i]){16 for(j=i;j<mxn;j+=i){17 if(!phi[j])phi[j]=j;18 phi[j]=phi[j]/i*(i-1);19 }20 }21 for(i=1;i<mxn;i++)sum[i]=sum[i-1]+phi[i];22 return;23 }24 int ans;25 int n;26 int main(){27 Euler();28 while(scanf("%d",&n) && n){29 printf("%d\n",2*sum[n]-1);30 }31 return 0;32 }
UVa10820 Send a Table
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。