枚举题。
1 #include <iostream>
2 #include <string>
3 #include <algorithm>
4 #include <string.h>
5 #include <vector>
6 #include <math.h>
7 #include <time.h>
8 #include <queue>
9 #include <set>
10 using namespace std;
11
12 const int MAX = 125005;
13
14 struct NODE
15 {
16 int a, b;
17 NODE(int aa, int bb) : a(aa), b(bb) {}
18 NODE() {}
19 bool operator < (const NODE &t) const
20 {
21 if(b != t.b) return b < t.b;
22 else return a < t.a;
23 }
24 };
25
26 set<int>num;
27 vector<NODE>ans;
28
29 bool use[MAX];
30 int n, m;
31
32 void ready()
33 {
34 memset(use, false, sizeof(use));
35 for(int i = 0; i <= m; i++)
36 {
37 for(int j = 0; j <= m; j++)
38 {
39 use[i * i + j * j] = true;
40 num.insert(i * i + j * j);
41 }
42 }
43 }
44
45 int getMaxD(int a, int b)
46 {
47 return (b - a) / (n - 1) + 1;
48 }
49
50 int getMaxNum()
51 {
52 int res = -1;
53 set<int>::iterator it;
54 for(it = num.begin(); it != num.end(); it++)
55 {
56 res = max(res, *it);
57 }
58 return res;
59 }
60
61 void go()
62 {
63 //枚举起点
64 set<int>::iterator it;
65 int maxNum = getMaxNum();
66 for(it = num.begin(); it != num.end(); it++)
67 {
68 int beg = *it;
69 int i, j;
70 //枚举公差
71 int d = getMaxD(beg, maxNum);
72 for(i = 1; i <= d; i++)
73 {
74 //判是否够长
75 for(j = 0; j < n; j++)
76 {
77 if(use[beg + i * j] == false) break;
78 }
79 if(j >= n) ans.push_back(NODE(beg, i));
80 }
81 }
82 if(ans.size() == 0)
83 {
84 printf("NONE\n");
85 return;
86 }
87 sort(ans.begin(), ans.end());
88 for(int i = 0; i < ans.size(); i++)
89 {
90 printf("%d %d\n", ans[i].a, ans[i].b);
91 }
92 }
93
94 int main()
95 {
96 freopen("ariprog.in", "r", stdin);
97 freopen("ariprog.out", "w", stdout);
98
99 scanf("%d%d", &n, &m);
100 ready();
101 go();
102 }