Farey Sequence

题目

F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}
Fn表示分子分母小于等于n不可约的分数，之后给n，让算出Fn一共有多少个不可约的分数

分析

不可约其实就是互质，而计算互质就很容易想到欧拉函数，所以这题打一个欧拉函数值的表，然后求个前缀和，就可以了

AC代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+10;
ll E[maxn],F[maxn];
ll N;
void init()
{
    E[1] = 1;
    for(ll i=2;i<maxn;i++){
        if(!E[i])
            for(ll j=i;j<maxn;j+=i){
                if(!E[j]) E[j]=j;
                E[j] = E[j]/i*(i-1);
            }
    }
    for(ll i =2;i<maxn;i++){
        F[i] = F[i-1] + E[i];
    }
}

int main(){
    init();
    while(scanf("%lld",&N)){
        if(N ==0) break;
        printf("%lld\n",F[N]);
    }
    return 0;
}