[USACO][Section 1.4][搜索] Arithmetic Progressions

题目大意：

给出两个整数n、m。要求找出一个n位等差数列，其元素属于集合{ p*p+q*q | 0<=p,q<=m }。

思路：

简单暴搜，具体思路见代码。

代码：

/*
ID: lujunda1
LANG: C++
PROG: ariprog
*/
#include
#include
using namespace std;
bool s[125001];//250*250*2
int n,m;
bool check(int start,int dif)
//判断是否存在从start开始，差为dif的n位等差数列。 
{
    for(int i=0;i<n;i++)
        if(!s[start+dif*i])
            return false;
    return true;
}
void solve()
{
    int total=0;
    for(int i=1;i<=2*m*m/(n-1);i++)
    //i表示等差数列的差值，范围是[1,2*m*m/(n-1)]。 
        for(int j=0;j<=2*m*m-i*(n-1);j++)
        //j表示等差数列的起始位置,范围是[0,2*m*m-i*(n-1)]。 
            if(check(j,i))
            {
                total++;
                printf("%d %d\n",j,i);
            }
    if(!total)
    //不存在符合要求的等差数列时，输出“NONO”。 
        printf("NONE\n");
}
int main()
{
    freopen("ariprog.in","r",stdin);
    freopen("ariprog.out","w",stdout);
    for(int i=0;i<125001;i++)
        s[i]=false;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=m;i++)
        for(int j=i;j<=m;j++)
        //枚举出所有p*p+q*q。 
            s[i*i+j*j]=true;
    solve();
}