本题跟POJ3090和POJ2478基本一个意思，很简单。
- #include <iostream>
- #define N 1000005
- typedef unsigned long long LL;
- LL p[N];
- void phi()
- {
- LL i,j;
- for(i=1;i<N;i++) p[i]=i;
- for(i=2;i<N;i+=2) p[i]>>=1;
- for(i=3;i<N;i+=2)
- {
- if(p[i]==i)
- {
- for(j=i;j<N;j+=i)
- {
- p[j]=p[j]/i*(i-1);
- }
- }
- }
- }
- int main()
- {
- LL n;
- phi();
- for(LL i=2;i<N;i++)
- p[i]+=p[i-1];
- while(std::cin>>n)
- {
- std::cout<<2*p[n]+1<<std::endl;
- }
- return 0;
- }