POJ 2478 题意：给定一个数n，求小于或等于n的数中两两互质组成的真分数的个数。
POJ 3090 题意：一个(0, n)*(0, n)的图，从点（0，0）到点（x，y）画线段不经过其它点，问能画多少条。
思路：
POJ3090
1×1只有一个斜率为0的 2×2斜率有0,1/2（0已经算过了，以后不再算了），其实就多了一个斜率为1/2的。 3×3的时候，有1/3,2/3两个，比以前多了2个 4×4的时候，有1/4,2/4（1/2已经有过了）,3/4，所以也是2个 5×5的时候，有1/5,2/5,3/5,4/5，之前都没有，所以多了4个 6×6得到时候，有1/6,2/6（1/3已经有了）,3/6(1/2已经有了),4/6(2/3已经有了),5/6，所以只剩2个。
分子和分母能够约分的，前面都已经有过了，所以每次要加的个数就是分子和分母互质的个数，也就是欧拉函数
（POJ2478同理）
POJ3090代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 1e3+5; int phi[maxn], p[maxn], pNum; bool f[maxn]; int sum[maxn]; void init() { for(int i = 2; i < maxn; i++) { if(!f[i]) { p[pNum++] = i; phi[i] = i-1; } for(int j = 0; j < pNum && p[j]*i < maxn; j++) { f[p[j]*i] = 1; if(i%p[j] == 0) { phi[p[j]*i] = phi[i]*p[j]; break; } else phi[p[j]*i] = phi[i]*(p[j]-1); } } } int main(void) { init(); phi[1] = 1; for(int i = 1; i < maxn; i++) sum[i] = sum[i-1]+phi[i]; int t, ca = 1; cin >> t; while(t--) { int x; scanf("%d", &x); printf("%d %d %d\n", ca++, x, sum[x]*2+1);//加1是对角线，*2是对称的上面的三角形 } return 0; }