题目链接：
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 14230 | Accepted: 5624 |
Description
Input
Output
Sample Input
2 3 4 5 0
Sample Output
1 3 5 9
题意：问满足a/b with 0 < a < b <= n and gcd(a,b) = 1,的数对有多少个;
思路：dp[i]=dp[i-1]+n的欧拉函数;
AC代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=1e6+2; long long dp[N],a[N]; int get_a() { memset(a,0,sizeof(a)); for(int i=2;i<N;i++) { if(!a[i]) { for(int j=i;j<N;j+=i) { if(!a[j])a[j]=j; a[j]=a[j]/i*(i-1); } } } } int fun() { get_a(); dp[1]=0; dp[2]=1; for(int i=3;i<N;i++) { dp[i]=dp[i-1]+a[i]; } } int main() { int n; fun(); while(1) { scanf("%d",&n); if(!n)break; cout<<dp[n]<<"\n"; } return 0; }
poj-2478 Farey Sequence(dp,欧拉函数)
原文：http://www.cnblogs.com/zhangchengc919/p/5272085.html