题意：定义 Fn 序列表示一串 <1 的分数，分数为最简分数，且分母 ≤n 。问该序列的个数。(2≤N≤10^6)
解法：先暴力找规律（代码见屏蔽处），发现 Fn 序列的个数就是 Φ(1)~Φ(n) 的和。于是用欧拉筛预处理就好了。
注意——求前缀和要用 long long 的类型。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 #define N (int)1e6+10 7 typedef long long LL; 8 9 int pr=0; 10 int v[N],phi[N],prim[N]; 11 LL sphi[N]; 12 13 int gcd(int a,int b) {return b?gcd(b,a%b):a;} 14 void get_prime() 15 { 16 memset(v,0,sizeof(v)); 17 for (int i=2;i<=N-10;i++) 18 { 19 if (!v[i]) prim[++pr]=i, phi[i]=i-1; 20 for (int j=1;j<=pr && i*prim[j]<=N-10;j++) 21 { 22 v[i*prim[j]]=1; 23 if (i%prim[j]==0) 24 { 25 phi[i*prim[j]]=phi[i]*prim[j]; 26 break; 27 } 28 else phi[i*prim[j]]=phi[i]*phi[prim[j]]; 29 } 30 } 31 sphi[1]=0; 32 for (int i=2;i<=N-10;i++) 33 sphi[i]=sphi[i-1]+phi[i]; 34 } 35 int main() 36 { 37 get_prime(); 38 int n; 39 while (1) 40 { 41 scanf("%d",&n); 42 if (!n) break; 43 /*int cnt=0,h=0; 44 for (int i=1;i<n;i++) 45 { 46 for (int j=i+1;j<=n;j++) 47 if (gcd(i,j)==1) cnt++; 48 h+=phi[i+1]; 49 } 50 printf("%d %d ",cnt,h);*/ 51 printf("%lld ",sphi[n]); 52 } 53 return 0; 54 }