uva 10820 - Send a Table（歐拉phi函數的應用）

本題的意思是：

輸入n，有多少個二進制組（x，y）滿足：1<=x,y<=n,且x和y互素。

答案是2*f(n)+1    f(n)=phi(2)+phi(3)+...+phi(n);

#include<cstdio>
#include<cstring>
#include<algorithm>

const int maxn = 50005;
int phi[maxn];
long long f[maxn];

void phi_table(int n,int* phi)
{
    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);
            }
        }
    }
    f[2]=phi[2];
    for(int i=3;i<=maxn;i++)
    {
        f[i]=f[i-1]+phi[i];
    }
}

int main()
{
    int n;
    phi_table(maxn,phi);
    while(scanf("%d",&n)&& n)
    {
        printf("%lld\n",2*f[n]+1);
    }
    return 0;
}
           

打表查找