一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)的数列。

在这个问题中a是一个非负的整数，b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p的平方 + q的平方的数的集合,其中p和q为非负整数)S中长度为n的等差数列。

思路：先算出双平方数集合，m^2的食府，去重。然后，穷举起点和差（即等差数列的第二项），一开始有穷举了后面所有的项，n^3算法，超时稳稳地；后来做了个bool数组，然后直接加差值，若不存在就break，若当前值大于最大值也break，n^2m的算法，稳过。

code：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct use{
    int a,b;
}ans[100001],an;
int shu[200000]={0};
bool us[200000]={false};
int my_comp(const use &x,const use &y)
{
    if (x.b<y.b) return 1;
    if (x.b==y.b&&x.a<y.a) return 1;
    return 0;
}
int main()
{
    int sum,n,m,i,j,k,tot=0,size,ansi=0,la,maxn=0;
    scanf("%d%d",&n,&m);
    for (i=0;i<=m;++i)
      for (j=i;j<=m;++j)
      {
           ++tot;
           shu[tot]=i*i+j*j;
           us[shu[tot]]=true;
           maxn=max(maxn,shu[tot]);
      }
    sort(shu+1,shu+tot+1);
    size=unique(shu+1,shu+tot+1)-shu-1;
    tot=size;
    ansi=1;
    for (i=1;i<tot;++i)
      for (j=i+1;j<=tot;++j)
      {
          an.a=shu[i];
          an.b=shu[j]-shu[i];
          la=shu[j];
          sum=2;
          while (sum<n)
          {
              if (la>=maxn) break;
              if (!us[la+an.b]) break;
              la=la+an.b;
              ++sum;
          }
          if (sum==n)
          {
              ans[ansi].a=an.a;
              ans[ansi].b=an.b;
              ++ansi;
          }
      }
    --ansi;
    if (ansi==0) printf("NONE\n");
    else
    {
      sort(ans+1,ans+ansi+1,my_comp);
      for (i=1;i<=ansi;++i)
        printf("%d %d\n",ans[i].a,ans[i].b);
    }
}

2205：