Posted on 2009-03-21 18:54
superman 閱讀(120)
評論(0) 編輯 收藏 引用 所屬分類:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 struct Record
6 {
7 int a, b;
8
9 bool operator < (const Record & r) const
10 {
11 if (b == r.b)
12 return a < r.a;
13 return b < r.b;
14 }
15 } rec[10000];
16
17 int recCnt;
18
19 int n, m;
20 int bisqCnt, bisq[125000 + 1];
21 bool isBisq[125000 + 1];
22
23 int main()
24 {
25 freopen("ariprog.in", "r", stdin);
26 freopen("ariprog.out", "w", stdout);
27
28 cin >> n >> m;
29
30 for (int p = 0; p <= m; p++)
31 for (int q = 0; q <= m; q++)
32 isBisq[p * p + q * q] = true;
33
34 for (int i = 0; i <= 2 * m * m; i++)
35 if (isBisq[i])
36 bisq[bisqCnt++] = i;
37
38 for (int i = 0; i <= bisqCnt - n; i++)
39 {
40 for (int j = i + 1; j <= bisqCnt - n + 1; j++)
41 {
42 int a = bisq[i];
43 int b = bisq[j] - bisq[i];
44
45 int k;
46 for (k = 2; k < n; k++)
47 {
48 if (a + b * k > 2 * m * m)
49 break;
50 if (isBisq[a + b * k] == false)
51 break;
52 }
53 if (k == n)
54 {
55 rec[recCnt].a = a;
56 rec[recCnt].b = b;
57 recCnt++;
58 }
59 }
60 }
61
62 sort(rec, rec + recCnt);
63
64 if (recCnt == 0)
65 cout << "NONE" << endl;
66
67 for (int i = 0; i < recCnt; i++)
68 cout << rec[i].a << ' ' << rec[i].b << endl;
69
70 return 0;
71 }
72