poj2478（欧拉函数）

题目链接：https://vjudge.net/problem/POJ-2478

题意：给定n，输出集合中元素的数量，集合中的元素为最简小于1的分数，分子分母均属于[1,n-1]。

思路：理清题意后就是输入n，输出[1,n]区间所有数的欧拉函数之和。要注意结果会超出int范围。

AC代码：

#include<cstdio>

using namespace std;

typedef long long LL;

const int maxn=;

int eu[maxn],n;

LL sum[maxn];

void eular(){

    for(int i=;i<=;++i){

        if(!eu[i])

            for(int j=i;j<=;j+=i){

                if(!eu[j]) eu[j]=j;

                eu[j]=eu[j]/i*(i-);

            }

        sum[i]=sum[i-]+eu[i];

    }

}

int main(){

    eular();

    while(scanf("%d",&n),n)

        printf("%lld\n",sum[n]);

    return ;

}