题目链接：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=1000005; int eu[maxn],n; LL sum[maxn]; void eular(){ for(int i=2;i<=1000000;++i){ if(!eu[i]) for(int j=i;j<=1000000;j+=i){ if(!eu[j]) eu[j]=j; eu[j]=eu[j]/i*(i-1); } sum[i]=sum[i-1]+eu[i]; } } int main(){ eular(); while(scanf("%d",&n),n) printf("%lld\n",sum[n]); return 0; }
原文：https://www.cnblogs.com/FrankChen831X/p/10832467.html