ariprog.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 83 行

{
ID:maigoak1
PROG:ariprog
}

program ariprog;
const
  maxm=250;
  maxbiscount=21047;
  maxseqs=10000;
var
  fin,fout:text;
  isbis:array[0..sqr(maxm)*2]of boolean;
  bis:array[1..maxbiscount]of longint;
  a:array[1..maxseqs]of longint;
  n,m,i,j,d,biscount,anscount:longint;
procedure check;
  var
    t,k:longint;
  begin
    t:=bis[i]+d;
    for k:=3 to n do begin
      inc(t,d);
      if not isbis[t] then exit;
    end;
    inc(anscount);
    a[anscount]:=d shl 17+i;
  end;
procedure qsort(s,t:longint);
  var
    p,i,j,tmp:longint;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tmp:=a[p];a[p]:=a[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (a[j]>tmp) do dec(j);
      if i=j then break;a[i]:=a[j];inc(i);
      while (i<j) and (a[i]<tmp) do inc(i);
      if i=j then break;a[j]:=a[i];dec(j);
    until i=j;
    a[i]:=tmp;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
begin
  assign(fin,'ariprog.in');
  reset(fin);
  read(fin,n,m);
  close(fin);

  fillchar(isbis,sizeof(isbis),0);
  for i:=0 to m do
    for j:=i to m do
      isbis[i*i+j*j]:=true;
  biscount:=0;
  m:=m*m*2;
  for i:=0 to m do
    if isbis[i] then begin
      inc(biscount);bis[biscount]:=i;
    end;

  assign(fout,'ariprog.out');
  rewrite(fout);
  anscount:=0;
  for i:=1 to biscount-1 do
    for j:=i+1 to biscount do begin
      d:=bis[j]-bis[i];
      if bis[i]+d*(n-1)>m then break;
      check;
    end;

  if anscount=0 then
    writeln(fout,'NONE')
  else begin
    qsort(1,anscount);
    for i:=1 to anscount do
      writeln(fout,bis[a[i] and 131071],' ',a[i] shr 17);
  end;
  close(fout);
end.