Farey Sequence（欧拉函数）

题意：给出式子F F中分子分母互质，且分子小于分母

例：

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项和，直接求解欧拉函数值的方法不行，由于用此法就是O（n^2)复杂度。採用递推式求解是O(nlogn)复杂度

代码例如以下：

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <math.h>

#include <vector>

#include <string>

#include <utility>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

long long euler(long long  n){ //返回euler(n)

     long long  res=n,a=n;

     for(long long  i=2;i*i<=a;i++){

         if(a%i==0){

             res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出

             while(a%i==0) a/=i;

         }

     }

     if(a>1) res=res/a*(a-1);

     return res;

}

//欧拉函数值直接求法，没用上，超时

long long a[1000010];

int main(){

    for(long long i=1;i<=1000005;i++)a[i]=i;

    for(long long i=2;i<=1000005;i+=2)a[i]/=2;

    for(long long i=3;i<=1000005;i++)if(a[i]==i){

        for(long long j=i;j<=1000005;j+=i)

        a[j]=a[j]/i*(i-1);

    }//递推公式  打表时非常好用

    for(long long i=3;i<=1000005;i++){

        a[i]+=a[i-1];

    }

    long long n;

    while(scanf("%I64d",&n)!=EOF){

        if(n==0)break;

        printf("%I64d\n",a[n]);

    }

    return 0;

}