例10-7 uva10820（欧拉）

题意：输入n，要求满足1≤x,y≤n，且x,y互素的个数。

若输入2，则答案3为(1,1),(1,2),(2,1);所以欧拉函数求出所有数的phi值，除了1之外都加上phi值的2倍即可

通过推导：

phi[n] = n*(1-1/p1)*......*(1-1/pn)            /*pi表示n的素因子，求出小于n与且与其互素的数

 

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 50000;
int phi[N + 5];

void phi_tab()
{
    for(int i = 2; i <= N; i++)
        phi[i] = 0;
    phi[1] = 1;
    for(int i = 2; i <= N; i++)
    {
        if(!phi[i])
            for(int j = i; j <= N; j+=i)
            {
                if(!phi[j])
                    phi[j] = j;
                phi[j] = phi[j]/i*(i-1);
            }
    }
}


int main()
{
    int n;
    phi_tab();
    while(scanf("%d",&n)!=EOF && n)
    {
        int ans = 1;
        for(int i = 2;i <= n;i++)
            ans+=2*phi[i];
        printf("%d\n",ans);
    }
    return 0;
}