A． 等差数列
一．题目描述：
一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)的数列。
在这个问题中a是一个非负的整数，b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p的平方 + q的平方的数的集合,其中p和q为非负整数)S中长度为n的等差数列。
二．格式
时间限制: 5 秒
题目名称: ariprog
输入格式:
(file ariprog.in)
第一行: N(3<= N<=25),要找的等差数列的长度。
第二行: M(1<= M<=250),搜索双平方数的上界0 <= p,q <= M。
输出格式:
(file ariprog.out)
如果没有找到数列,输出“NONE”。
如果找到了，输出一行或多行, 每行由二个整数组成:a,b。 a为等差数列的第一个值，b为等差数列的公差。
这些行应该先按b排序再按a排序。
所求的等差数列将不会多于10,000个。
三．
样例输入：
5
7
样例输出：
1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24
分析：
对于限制时间比较宽松的这个题呀~~~~~暴力穷举就可以了~~~~~~
按照题意，先是确定所有的双平方数，然后根据给的上限，把范围内的双平方数储存起来。
（哎呀，好懒啊，不想写了=.=）
我的代码里有注释。。。以后有闲时间了再来补充吧。╮(╯▽╰)╭
不说了，上代码。
#include<iostream>
#include<cstring>
using namespace std;
bool is[]; //记录谁是双平方数的bool数组
int a[]; //由于所给上限是250，则最大的数为250*250*2
int main(){ //n是给的等差数列的长度，top是所给搜索双平方数的上界
int n,top,k=,tole,num=; //k初始化为0，最后为的储存双平方数数组的总长度。
scanf("%d%d",&n,&top); //tole为公差 ，num记录满足条件的数组的个数 ，用于判断是否在后面的bool f=0时
for(int i=;i<=top;i++) //把所有的数是否是双平方数记录下来
for(int j=;j<=top;j++)
is[i*i+j*j]=; //标记范围内的所有双平方数
for(int i=;i<=top*top*;i++) //把上限范围内的双平方数储存起来
if(is[i])
a[k++]=i; //一共有k个数 ，a[k]数组储存所有的双平方数
int maxt=(top*top*)/(n-); //前面先定义了公差为tole，maxt为公差的最大范围 前面的num为记录等差数列的个数
for (tole=;tole<=maxt;tole++){ //tole为公差 ，a[i]为首项 ，对于每一个可能的公差，去检查对于a[i]每一个元素，是否有等差数列的可能
for(int i=;a[i]+(n-)*tole<=top*top*&&i<k;i++){ //a[i]+（n-1）*l为第i项
bool f=;
for(int j=;j<n&&f;j++) //检查对于每个等差数列，它的每一项元素都在双平方数组中
if(!is[a[i]+j*tole]){ //如果有一项没有在bool数组里，则令bool值f为false
f=;
}
if(f){ //在经过对等差数列每一项检查后，f仍为真，则满足题意
printf("%d %d\n", a[i],tole); //满足条件的数列，输出首项和公差
num++; //num记录满足条件的数列的个数
}
}
}
if (!num) //num为0，则输出NONE
printf("NONE");
return ;
}