Description
给出一个数字N，求sigma(phi(i)),1<=i<=N Input
正整数N。N<=2*10^9 Output
输出答案。 Sample Input
10 Sample Output
32 HINT
杜教筛入门 http://blog.csdn.net/popoqqq/article/details/45023331
#include<bits/stdc++.h> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,0x3f,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define MEMx(a,b) memset(a,b,sizeof(a)); #define INF (0x3f3f3f3f) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") #define ALL(x) (x).begin(),(x).end() typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (10000000+100) ll p[MAXN],tot,phi[MAXN]; bool b[MAXN]={0}; void make_prime(int n) { tot=0; phi[1]=1; Fork(i,2,n) { if (!b[i]) p[++tot]=i,phi[i]=i-1; For(j,tot) { if (i*p[j]>n) break; b[i*p[j]]=1; phi[i*p[j]]=phi[i]*phi[p[j]]; if (i%p[j]==0) { phi[i*p[j]]= phi[i]*p[j]; break; } } } } map<ll,ll> h; map<ll,ll>::iterator it; ll calc_phi(ll n) { if (n<=1e7) return phi[n]; if ((it=h.find(n))!=h.end()) return (*it).se; ll last=1,ans=n*(n+1)/2; for(int i=2;i<=n;i=last+1) { last=n/(n/i); ans-=calc_phi(n/i)*(last-i+1); } return h[n]=ans; } int main() { // freopen("bzoj4805.in","r",stdin); // freopen(".out","w",stdout); make_prime(1e7); Fork(i,2,1e7) phi[i]+=phi[i-1]; ll n; cin>>n; cout<<calc_phi(n); return 0; }