superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Section 1.4 - Arithmetic Progressions

Posted on 2009-03-21 18:54 superman 阅读(117) 评论(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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理