問(wèn)題:
http://poj.org/problem?id=3090思路:
首先可以觀察得到這樣的點(diǎn)集是對(duì)稱(chēng)的，只需要求一半即可
這里，我采用了模擬的方法，直接去掉擋住的點(diǎn)
結(jié)果TLE，然后發(fā)現(xiàn)可以打表，隨即AC，打表真是強(qiáng)大啊呵呵...
ps.
據(jù)說(shuō)這題與什么歐拉函數(shù)有關(guān)系，沒(méi)有深究
代碼:
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 }