poj 2478 http://poj.org/problem?id=2478
思路：欧拉函数基础题，可以看出n+1与n的区别只是多加了一个phi(n)的大小而已，记得会超long long 就好了
素数筛法：学习博客
/************************************************************** Problem:poj 2478 User: youmi Language: C++ Result: Accepted Time:94MS Memory:10884K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d ",a) #define ptlld(a) printf("%I64d ",a) #define rep0(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define rep_1(i,n) for(int i=n;i>=1;i--) #define rep_0(i,n) for(int i=n-1;i>=0;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define esp 1e-6 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl using namespace std; typedef long long ll; int n; const int maxn=1000000+10; bool isprime[maxn]; int prime[maxn]; ll phi[maxn]; int tot=0; void get_prime() { tot=0; memset(isprime,true,sizeof(isprime)); isprime[0]=isprime[1]=false; prime[tot++]=2; for(int i=3;i<maxn;i++) { if(isprime[i]) { prime[tot++]=i; for(ll j=i;1ll*i*j<maxn;j+=2) isprime[i*j]=false; } } } void get_phi() { phi[1]=1; for(int i=1;i<maxn;i++) { for(int j=0;j<tot&&1ll*i*prime[j]<maxn;j++) { if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif get_prime(); get_phi(); for(int i=3;i<maxn;i++) phi[i]+=phi[i-1]; while(~sc(n)&&n) { printf("%lld ",phi[n]); } }
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <stack> using namespace std; const int maxn=1000000+20; typedef long long ll; int n; ll phi[maxn]; void init()//nlog(n)的复杂度 { for(int i=1;i<=maxn-10;i++) phi[i]=i; for(int i=2;i<=maxn-10;i+=2) phi[i]/=2; for(int i=3;i<=maxn-10;i+=2) { if(phi[i]==i) { for(int j=i;j<=maxn-10;j+=i) phi[j]=(phi[j]/i)*(i-1); } } for(int i=3;i<=maxn-10;++i) phi[i]+=phi[i-1]; } int main() { //freopen("in.txt","r",stdin); init(); while(~scanf("%d",&n)&&n) { printf("%lld ",phi[n]); } return 0; }