1354. 等差数列

1. 预处理出双平方数集合
2. 枚举双平方数中的一对数作为等差数列的首项和第二项

剪枝：

1. 计算出当前等差数列的末项，last=x+(n-1)*d比双平方数集合中最大的数还要大，则无需判断其是否能构成长度为\(n\)的等差数列。
2. 如果当前公差比双平方数集合中最大的数还要大，那么比当前公差还要大的公差显然也没有枚举的必要了。

由于剪枝\(2\)的存在，需要对原双平方数集合进行排序。

const int N=251*251+10,M=250*250*2+10;
int a[N];
bool vis[M];
PII ans[10010];
int n,m;
int cnt;
int tot;

bool check(int x,int d)
{
    for(int i=2;i<n;i++)
    {
        x+=d;
        if(!vis[x]) return false;
    }
    return true;
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i <= m; i++)
        for (int j = i; j <= m; j++)
        {
            int x=i*i+j*j;
            if(!vis[x]) a[cnt++]=x;
            vis[x]=true;
        }

    sort(a,a+cnt);

    for (int i = 0; i < cnt; i++)
        for (int j = i+1; j < cnt; j++)
        {
            int x=a[i],d=a[j]-a[i];
            int last = x+(n-1)*d;
            if(last > a[cnt-1]) break;
            if (check(a[j],d)) ans[tot++]={x,d};
        }

    if (tot == 0) puts("NONE");
    else
    {
        sort(ans, ans+tot, [](PII a, PII b){
            if (a.se != b.se) return a.se < b.se;
            return a.fi < b.fi;
        });
        for (int i = 0; i < tot; i++)
            cout << ans[i].fi << ‘ ‘ << ans[i].se << endl;
    }
    //system("pause");
    return 0;
}

1354. 等差数列

原文：https://www.cnblogs.com/fxh0707/p/14805902.html