Limit is too small

The problem limits are too small.

You can get ac with the O(N^2) algorithm which is VERY

straightforward. The limit should force you to use the O

(log N) algorithm to compute X^N (%M)

Re: Limit is too small

> The problem limits are too small.

> You can get ac with the O(N^2) algorithm which is VERY

> straightforward. The limit should force you to use the O

> (log N) algorithm to compute X^N (%M)

O(log N) !? Isn't it O(MlogN) ?

well,if it's really O(log N) , please tell me how :)

Re: Limit is too small

I got AC with 0.031 373 KB using brute force.

This is the dummest task I made. Tell them to read the

O(M log N) algorith in Introduction in algo(Coreman)

This sadly is my AC source:

var i,j,k,l,m,n:longint;

ok:boolean;

begin

readln(n,m,k);

for i:=0 to m-1 do

begin

l:=i;

for j:=1 to n-1 do

l:=(l*i) mod m;

if l mod m=k then

begin

write(i,' ');

ok:=true;

end;

end;

if not ok then write(-1);

end.

*Edited by author 10.05.2004 17:49*

Re: Limit is too small

Hello, explain to me why you use

l:=(l*i) mod m;(...mod m)?!!

Why?