问题:
http://poj.org/problem?id=3090思路:
首先可以观察得到这样的点集是对称的，只需要求一半即可
这里，我采用了模拟的方法，直接去掉挡住的点
结果TLE，然后发现可以打表，随即AC，打表真是强大啊呵呵...
ps.
据说这题与什么欧拉函数有关系，没有深究
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 1001
5 int N, points[MAX_LEN][MAX_LEN];
6 int result[MAX_LEN];
7
8 /* Attention: symmetrical */
9 void
10 solve()
11 {
12 int i, j, k, count = 0;
13 memset(points, 0, sizeof(points));
14 for(i=1; i<MAX_LEN; i++) {
15 for(j=0; j<i; j++) {
16 if(!points[i][j])
17 ++count;
18 for(k=1; i*k<MAX_LEN&&j*k<MAX_LEN; k++)
19 points[i*k][j*k] = 1;
20 }
21 result[i] = count;
22 }
23 }
24
25 int
26 main(int argc, char **argv)
27 {
28 int i, tests;
29 solve();
30 scanf("%d", &tests);
31 for(i=1; i<=tests; i++) {
32 scanf("%d", &N);
33 printf("%d %d %d\n", i, N, ((result[N]<<1)+1));
34 }
35 }