poj 3478 poj 3090（欧拉函数的应用）

3478题目意思是Farey序列是由一系列不能约分的分数a/b（0<a<b<=n且gcd(a,b)=1）按照递增的顺序组成的，然后给出了Fn的前几项，让你计算Fn中有多少个分数.

很明显Fn中的数的个数就是分别与(2,3,4.....n-1,n)互质的数的个数的和。也就是求欧拉函数的前n项和。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 1000000;

typedef long long LL;

LL phi[maxn+1];

void init()
{
    LL i,j;
    for(i=1;i<=maxn;i++) phi[i] = i;
    for(i=2;i<=maxn;i+=2) phi[i]/=2;
    for(i=3;i<=maxn;i+=2){
        if(phi[i] == i){
            for(j=i;j<=maxn;j+=i){
                phi[j] = phi[j]/i*(i-1);
            }
        }
    }
    for(i=3;i<maxn+1;i++){
        phi[i]+=phi[i-1];
    }
}

int main()
{
     init();
     int n;
     while(cin>>n&&n){
        printf("%lld
",phi[n]);
     }

    return 0;
}

 3090的情况跟3478差不多，但是要注意的可见点的情况是以x=y这条直线对称的，所以最后的答案是2*phi[n]+1，x=y也算。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 1000;

typedef long long LL;

LL phi[maxn+1];

void init()
{
    LL i,j;
    for(i=1;i<=maxn;i++) phi[i] = i;
    for(i=2;i<=maxn;i+=2) phi[i]/=2;
    for(i=3;i<=maxn;i+=2){
        if(phi[i] == i){
            for(j=i;j<=maxn;j+=i){
                phi[j] = phi[j]/i*(i-1);
            }
        }
    }
    for(i=2;i<maxn+1;i++){
        phi[i]+=phi[i-1];
    }
}

int main()
{
     init();
     int n;
     int cas;
     cin>>cas;
     for(int i=1;i<=cas;i++){
        cin>>n;
        printf("%d %d %d
",i,n,2*phi[n]+1);
     }

    return 0;
}