题解 | #Farey Sequence#

思路

这是一道裸的欧拉函数题目，先线性预处理。
对于所有n>2的欧拉函数进行前缀和，然后直接输出答案就可以了。

代码

#include<stdio.h>
typedef long long ll;
const int maxn=1e6+7;
int n,isn_pri[maxn],pri[maxn],phi[maxn],cnt;
ll sum[maxn];

void get(int N){
    isn_pri[1]=1;phi[1]=1;
    for(int i=2;i<=N;i++){
        if(!isn_pri[i]){
            pri[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&pri[j]*i<=N;j++){
            isn_pri[pri[j]*i]=1;
            if(i%pri[j]==0){
                phi[pri[j]*i]=phi[i]*pri[j];
                break;
            }else phi[pri[j]*i]=phi[i]*(pri[j]-1);
        }
    }
}

signed main(){
    get(maxn-5);
    for(int i=2;i<maxn;i++){
        sum[i]=sum[i-1]+phi[i];
    }
    while(scanf("%lld",&n)&&n){
        printf("%lld\n",sum[n]);
    }
    return 0;
}