這個,自己寫了一個代碼,很丑.觀摩了一些以C++為"母語"的OIer的代碼,學習了一些新的寫法.直接搜索是可以做的,因此我沒有更深入地思考過其他的解法.我發現我把學習C++當作自己學習目標的做法很大程度上淡化了我對算法的關注.
學習算法,看看《算法導論》之類的書很有好處,學習語言,觀摩別人的代碼是必不可少的,這是我這幾天一來的體會.
下面的代碼基本上就是按照人家的代碼打了一遍.不過很好理解,解釋也是多余的.
1 /*
2 ID:31440461
3 PROG:ariprog
4 LANG:C++
5 */
6 #include<iostream>
7 #include<algorithm>
8 using namespace std;
9 const int MAX=250*250*2+10;
10 bool flag[MAX]={};
11 int leg[MAX],size=0,res_cnt=0;
12 struct re
13 {
14 int a,b;
15 bool operator < (const re& x) const
16 {
17 return b<x.b || b==x.b && a<x.a;
18 }
19 }res[10000];
20
21 int main()
22 {
23 freopen("ariprog.in","r",stdin);
24 freopen("ariprog.out","w",stdout);
25 //memset(flag,0,sizeof(flag));
26 int n,m;
27 cin >> n >> m;
28 int max=m*m*2;
29 for (int i=0;i<=m ;++i )
30 for (int j=0;j<=m ;++j )
31 flag[i*i+j*j]=1;
32 for (int i=0;i<=max ;++i ) if (flag[i]) leg[size++]=i;
33
34 for (int i=0;i<size ;++i )
35 for (int j=i+1;j<size ;++j )
36 {
37 int d=leg[j]-leg[i];
38 if (leg[i]+(n-1)*d>max) break;
39 for (int k=2;k<n ;k++ )
40 if (!flag[leg[i]+k*d]) goto L1;
41 res[res_cnt].a=leg[i];
42 res[res_cnt++].b=d;
43 L1:;
44 }
45 sort(res,res+res_cnt);
46 if (!res_cnt) cout << "NONE" << endl;
47 else
48 for (int i=0;i<res_cnt ;i++ ) cout << res[i].a << ' ' << res[i].b << endl;
49 return 0;
50 }
51
52