等差数列Arithmetic Progressions题解(USACO1.4)

Arithmetic Progressions USACO1.4

An arithmetic progression is a sequence of the form a, a+b, a+2b, ..., a+nb where n=0,1,2,3,... . For this problem, a is a non-negative integer and b is a positive integer.

Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p2 + q2 (where p and q are non-negative integers).

INPUT:

N (3 <= N <= 25), the length of progressions for which to search

M (1 <= M <= 250), an upper bound to limit the search to the bisquares with 0 <= p,q <= M.

OUTPUT:

If no sequence is found, a single line reading `NONE'. Otherwise, output one or more lines, each with two integers: the first element in a found sequence and the difference between consecutive elements in the same sequence. The lines should be ordered with smallest-difference sequences first and smallest starting number within those sequences first.

There will be no more than 10,000 sequences.

此题目需要一些小的剪枝，详见注释。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define rint register int

const int MAXN=100000+5;

int a[MAXN];

int aa[10005],bb[10005];

bool tab[MAXN];

int n,m,cnt,tot,mx;

int main()

{

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

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

	scanf("%d%d",&n,&m);

	for(rint i=0;i<=m;++i)

		for(rint j=0;j<=m;++j)

			a[++cnt]=i*i+j*j,tab[a[cnt]]=1;//预处理双平方数表，快速查表

	sort(a+1,a+cnt);

	cnt=unique(a+1,a+cnt+1)-a-1;

	mx=m*m<<1;

	int r=mx/(n-1);//公差上界，最大的数除以要求的长度

	for(rint i=1;i<=r;++i)

	{

		for(rint j=1;j<=cnt;++j)

		{

			rint c=0;

			for(rint k=n-1;k>0&&a[j]+i*k<=mx;--k)//若超过max退出循环

                //从大到小枚举，不符合情况易退出

				if(!tab[a[j]+i*k]) //若有一个不符合条件即break

					break;

				else ++c;

			if(c==n-1)

			{

				aa[++tot]=a[j];

				bb[tot]=i;

			}

		}

	}

	if(tot==0)

		puts("NONE");

	else

		for(int i=1;i<=tot;++i)

			printf("%d %d\n",aa[i],bb[i]);

	return 0;

}