题目http://acm.hdu.edu.cn/showproblem.php?pid=4556
这个真的很纠结 以前老师叫我们看一下数论 没有 看导致不会做哦 每一次都是超时哦 很纠结 所以今天看了一下别人的代码
发现是 欧拉函数哦 其实当时我也想出是求每个数的质数哦,但是每次都是超时哦,没办法 下次一定要看看数论哦
具体ac代码
#include<iostream> #include<cstdio> using namespace std; #define max 1000001 int e[max]; void euler() { int i,j; for(i=1;i<max;i++) { e[i]=i; } for(i=2;i<max;i++) { if(e[i]==i) { for(j=i;j<max;j+=i) { e[j]=e[j]/i*(i-1); } } } } int main() { int i,n; euler(); __int64 sum,sum1; while(cin>>n) { sum=0; for(i=1;i<=n;i++) { sum+=e[i]; sum1=2*sum+1; } cout<<sum1<<endl; } return 0; }