1.4.3 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 singe 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)

{
ID: makeeca1
PROG: ariprog
LANG: PASCAL
}
Program ariprog;
const magic=0.618; maxn=21050;maxm=125010;maxt=10010;
Var b:array[0..maxm]of boolean;
    a:array[0..maxn]of longint;
//    x,y:array[0..maxt]of longint;
    n,m,i,j,t,max,len,ans,k,first,maxy:longint;   f:boolean;
{procedure swap(var xx,yy:longint);
var tt:longint;begin tt:=xx;xx:=yy;yy:=tt;end;
procedure qsort(l,r:longint);
var i,j,x1,y1:longint;
begin
  i:=l;j:=r;x1:=l+trunc((r-l)*magic);y1:=y[x1];x1:=x[x1];
  repeat
    while (y[i]<y1)or((y[i]=y1)and(x[i]<x1)) do inc(i);
    while (y[j]>y1)or((y[i]=y1)and(x[i]>x1)) do dec(j);
    if i<=j then begin swap(x[i],x[j]);swap(y[i],y[j]);inc(i);dec(j);end;
  until i>j;
  if i<r then qsort(i,r);
  if l<j then qsort(l,j);
end; }
Begin
  assign(input,'ariprog.in');reset(input);
  assign(output,'ariprog.out');rewrite(output);
  readln(n);
  readln(m);max:=0;
  fillchar(b,sizeof(b),0);
  fillchar(a,sizeof(a),0);
  for i:=0 to m do
    for j:=0 to m do
    begin
      t:=sqr(i)+sqr(j);
      b[t]:=true;
      if t>max then max:=t;
    end;;
  len:=0;
  for i:=0 to max do
  if b[i]then
  begin
    inc(len);
    a[len]:=i;
  end;
  ans:=0;
  maxy:=max div (n-1);
  for j:=1 to maxy do
  begin
    first:=a[1];
    k:=1;
    while first<=max-(n-1)*j do
    begin
      f:=true;
      for i:=1 to n-1 do
      if not b[first+i*j]then begin f:=false;break;end;
      if f then begin writeln(first,' ',j);inc(ans);end;
      inc(k);
      first:=a[k];
    end;
  end;
  if ans=0 then writeln('NONE');
  close(input);close(output);
End.