题目请点我

题解：

这道题的题意是找出集合里全部固定长度为N的等差数列。集合内的元素均为P^2+q^2的形式（0<=p,q<=M）。时间要求5s内。本着KISS，直接暴力。

可是后来竟超时了。检查后发现是map的问题，本想利用map实现常数级的查找。可是显然map内部不是这种。所以对于普通的数据类型。数据量不大（250^2+250^2）的情况下还是利用数组标记查找好一点，get。

代码实现：

/*

ID: eashion

LANG: C++

TASK: ariprog

*/

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <map>

#include <algorithm>

#define MAX 125000

using namespace std;

int N,M;

bool flag;

int num[MAX];

int mm[MAX];

bool test(int start,int len);

int main()

{

    freopen("ariprog.in","r",stdin);

    freopen("ariprog.out","w",stdout);

    while( scanf("%d%d",&N,&M) != EOF ){

        int pos = 0;

        flag = false;

        memset(mm,0,sizeof(mm));

        for( int i = 0; i <= M; i++ ){

            for( int j = 0; j <= M; j++ ){

                int tmp = i*i+j*j;

                if( mm[tmp] != 1 ){

                    num[pos] = tmp;

                    mm[tmp] = 1;

                    pos++;

                }

            }

        }

        sort(num,num+pos);

        int up_B = (num[pos-1]-num[0])/(N-1);

        for( int i = 1; i <= up_B; i++ ){

            for( int j = 0; j < pos; j++ ){

                if( test(num[j],i) ){

                    flag = true;

                    printf("%d %d\n",num[j],i);

                }

                if( num[j]+(N-1)*i > num[pos-1] ){

                    break;

                }

            }

        }

        if( flag == false ){

            printf("NONE\n");

        }

    }

    return 0;

}

bool test(int start,int len){

    int tmp = start;

    for( int i = 0; i < N; i++ ){

        if( mm[tmp] != 1 ){

            return false;

        }

        tmp += len;

    }

    return true;

}