简单的枚举题。
题意是在一个集合S中求等差数列，输出等差数列的首项与公差。集合S中的元素是两个非负数的平方和。题目给出等差数列的项数，集合元素的范围。
思路：用一个bool数组记录该位置的数是否属于集合S。如果直接枚举公差很容易超时。这里可以减枝，使用一个list数组将bool数组中有效的元素全部保存起来。这样取出首项与公比就更快速了。另外要优化的就是判断最后一项是否在集合S中。
/*
ID:seven4
LANG:C++
PROG:ariprog
*/
#include<stdio.h>
#include<algorithm>
using namespace std;bool temp[250*250*2+1];
int list[250*250*2+1];struct node
{int a,d;
}ans[10001];bool cmp( node a,node b )
{ if(a.d==b.d) return a.a<b.a;else return a.d<b.d;
}bool cmplist( int a,int b ){return a<b;}int main()
{freopen( "ariprog.in","r",stdin );freopen( "ariprog.out","w",stdout );int N,M;for( int i=0;i<=250*250*2;i++ )temp[i]=false;scanf( "%d %d",&N,&M );int top=M*M*2;for( int p=0;p<=M;p++ )for( int q=0;q<=M;q++ )temp[p*p+q*q]=true;int k=0;for( int i=0;i<=top;i++ )if( temp[i] ) list[k++]=i;sort( list,list+k,cmplist );//枚举首项a和等差dint t=0;for( int i=0;i<k;i++ ){for( int j=i+1;j<k;j++ ) {if( list[j]==list[i] )continue;int d=list[j]-list[i];if( (list[i]+(N-1)*d)>top )continue;bool flag=true;for( int s=1;s<N;s++ ){if( temp[list[i]+s*d]==false ){flag=false;break;}}if( flag ){ans[t].a=list[i];ans[t].d=d;t++;}}}if( t==0 )printf( "NONE\n" );else{sort( ans,ans+t,cmp );for( int i=0;i<t;i++ )printf( "%d %d\n",ans[i].a,ans[i].d );}return 0;
}