ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1528. Sequence

Why WA5?
Posted by [中山一中]Rabidstorm 26 Dec 2008 10:30
program Ural1528;

var
p:array[1..10000]of qword;
q,u,e:array[1..5000]of qword;
ans:array[1..5000]of qword;
m:qword;
a,n,max,x,y:longint;

procedure qsort(l,r:longint);

var
i,j:longint;
mid,swap:qword;

begin
i:=l;j:=r;mid:=u[(i+j)div 2];
repeat
while u[i]<mid do inc(i);
while u[j]>mid do dec(j);
if i<=j then
begin
swap:=u[i];u[i]:=u[j];u[j]:=swap;
swap:=q[i];q[i]:=q[j];q[j]:=swap;
swap:=e[i];e[i]:=e[j];e[j]:=swap;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;

begin
n:=0;max:=0;
repeat
if (x=0)and(y=0) then exit;
inc(n);inc(max);
if x>=y then begin
ans[n]:=0;
dec(max);
end else begin
q[max]:=x;u[max]:=y;e[max]:=n;
end;
until (x=0)and(y=0);
end;

function gcd(o,z:qword):qword;

begin
if z=0 then exit(o)
else exit(gcd(z,o-o div z*z));
end;

procedure main;

var
i,j,mu:longint;
o:qword;

begin
i:=1;
j:=1;
while i<=max do
begin
m:=1;
mu:=0;
o:=1;
while (i<=max)and(trunc(ln(m)/ln(10))+trunc(ln(u[i])/ln(10))-trunc(ln(o)/ln(10))<=18)do
begin
m:=m div o;
m:=m*u[i];
if mu<q[i] then mu:=q[i];
inc(i);
if i<=max then
if u[i]>m then o:=gcd(u[i],m)
else o:=gcd(m,u[i]);
end;
p[1]:=1;
for a:=2 to mu do
p[a]:=p[a-1]*a mod m;
for a:=j to i-1 do
ans[e[a]]:=p[q[a]]mod u[a];
j:=i;
end;
end;

procedure writedata;

begin
for a:=1 to n do
writeln(ans[a]);
end;

begin