USACO 1.4 Arithmetic Progressions

Arithmetic Progressions

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 p² + q² (where p and q are non-negative integers).

TIME LIMIT: 5 secs

PROGRAM NAME: ariprog

INPUT FORMAT

Line 1:	N (3 <= N <= 25), the length of progressions for which to search
Line 2:	M (1 <= M <= 250), an upper bound to limit the search to the bisquares with 0 <= p,q <= M.

SAMPLE INPUT (file ariprog.in)

5

7

OUTPUT FORMAT

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.

SAMPLE OUTPUT (file ariprog.out)

1 4

37 4

2 8

29 8

1 12

5 12

13 12

17 12

5 20

2 24

题目大意：给你n和m，n表示目标等差数列的长度（等差数列由一个非负的首项和一个正整数公差描述），m表示p,q的范围，目标等差数列的长度必须严格等于n且其中每个元素都得属于集合{x|x=p^2+q^2}(0<=p<=m,0<=q<=m)，按顺序输出所有的目标数列。
思路：其实很简单，就是枚举，枚举起点和公差，一开始有点担心会超时，弄的自己神烦意乱的，但是实际上并没有。。。。。下面附上代码

 /*

 ID:fffgrdcc1

 PROB:ariprog

 LANG:C++

 */

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int a[*],cnt=,n,m;

 int bo[];

 struct str

 {

     int a;

     int b;

 }ans[];

 int tot=;

 bool check(int a,int b)

 {

     int temp=a+b+b,tt=m-;

     while(tt--)

     {

         if(temp>n*n*||!bo[temp])return ;

         temp+=b;

     }

     return ;

 }

 bool kong(str xx,str yy)

 {

     return xx.b<yy.b||(xx.b==yy.b&&xx.a<yy.a);

 }

 int main()

 {

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

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

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

     for(int i=;i<=n;i++)

     {

         for(int j=i;j<=n;j++)

         {

                 bo[i*i+j*j]=;

         }

     }

     for(int i=;i<=n*n*;i++)

         if(bo[i])

             a[cnt++]=i;

     for(int i=;i<cnt;i++)

     {

         for(int j=i+;j<cnt;j++)

         {

             if(check(a[i],a[j]-a[i]))

             {

                 ans[tot].a=a[i];

                 ans[tot++].b=a[j]-a[i];

             }

         }

     }

     sort(ans,ans+tot,kong);

     if(!tot)printf("NONE\n");

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

     {

         printf("%d %d\n",ans[i].a,ans[i].b);

     }

     return ;

 }

巴特西