原文翻譯：
翻譯者：timgreen
轉載自：OIBH
一個等差數列是一個能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)
在這個問題中a是一個非負的整數，b是正整數。
寫一個程序來找出在雙平方數集合S中長度為n的等差數列。
雙平方數集合是所有能表示成p2＋q2的數的集合。
PROGRAM NAME: ariprog
INPUT FORMAT
第一行: N(3<= N<=25),要找的等差數列的長度。
第二行: M(1<= M<=250),搜索雙平方數的上界0 <= p,q <= M。
SAMPLE INPUT (file ariprog.in)
5
7
OUTPUT FORMAT
如果沒有找到數列,輸出`NONE'。
如果找到了，輸出一行或多行, 每行由于二個整數組成:a,b
這些行應該先按b排序再按a排序。
將不會有只多于10,000個等差數列。
SAMPLE OUTPUT (file ariprog.out)
1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24
這題的思路應該說還是比較容易想的，不過要已開始就想到不TLE的就有點難了，可以把形 如p^2+q^2的數都存起來，后來就可以直接去數組里面取了。
接下來就是找適合的a和b了。
我一開始的代碼是最原始的，就是一個一個找，
for(int i = 0;i < index1-n+1;i++)
{
a = num[i];
for(int j = i+1;j < index1;j++)
{
b = num[j]-a;
now = a+b;
count = 2;
if(a + b*(n-1) > max_num)//這里是表示不可能找到滿足條件的a和b
continue;
for(int k = j+1;k < index1;k++)
{
if(now+b == num[k])
{
now = num[k];
count++;
if(n == count)//如果找到，就退出
{
node[index2].a = a;
node[index2++].b = b;
break;
}
}
if(num[k] > now + b)//表示不可能找到合適的a和b
break;
}
}
可是這樣TLE，死在第7組數據上，聽說第8組更強悍的數據。
后來搜了份報告，發現挺不錯的，
代碼如下
for(int i = 0;i < index1-n+1;i++)
{
a = num[i];
for(int j = i+1;j < index1;j++)
{
b = num[j]-a;
now = a+b;
count = 2;
if(a + b*(n-1) > max_num)
continue;
can = true;
for(int k = 2;k < n;k++)
{
if(!isexict[a+b*k])//isexict[i]表示i可以表示成p^2+q^2不
{
can = false;
break;
}
}
if(can)
{
node[index2].a = a;
node[index2++].b = b;
}
}
}
我的思路是一直找，找合適的，但是上面這個就是找不合適的，這樣肯定會快，因為這里面不合適的多得多。這就是枚舉時不同的方法，差別很大啊
不過還有人能在第8組數據上之用0.63S，可是我的用了1.46S，看來還有更好的，繼續學習。
不過現在我再改了下，第8組數據也只要0.43S了，也就是把下第二個程序的
if(a + b*(n-1) > max_num)
continue;
中的continue;改成break;因為當這個不可能的時候，下面的b只會比這個還大，那肯定不行，所以就直接break了