题意：定义 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\n",cnt,h);*/
51 printf("%lld\n",sphi[n]);
52 }
53 return 0;
54 }