题目链接：https://vjudge.net/problem/POJ-2478
2 3 4 5 0Sample Output
1 3 5 9
思路：
1=1
3=1+2
5=1+2+2
9=1+2+2+4
...
由于1 2 2 4 4 ... 是欧拉值，故很容易想到是求欧拉值的前缀和，所以第一步将欧拉值打表出来，后来我一开始遍历用for循环求
和，超时了，所以这里还是要将前缀和存入表内，由于是从下标为2开始的，故求前缀和从下标为3开始
// // Created by hanyu on 2019/8/9. // #include <algorithm> #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <set> #include<math.h> #include<map> using namespace std; typedef long long ll; const int maxn=2e6+7; ll euler[maxn]; void value() { memset(euler,0,sizeof(euler)); euler[1]=1; for(int i=2;i<=maxn;i++) { if(!euler[i]) { for(int j=i;j<=maxn;j+=i) { if(!euler[j]) euler[j]=j; euler[j]=euler[j]/i*(i-1); } } } for(int i=3;i<=maxn;i++) euler[i]+=euler[i-1]; } int main() { int n; value(); while(~scanf("%d",&n)&&n) { printf("%lld\n",euler[n]); } return 0; }
Farey Sequence POJ - 2478 (欧拉函数 前缀和）
原文：https://www.cnblogs.com/Vampire6/p/11329981.html