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 1110. Power

Limit is too small
Posted by Scythe (Berinde Radu) 24 Nov 2001 10:42
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
Posted by MadPsyentist/Sam 15 Jan 2002 16:16
> 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
Posted by Dinu Adrian Florin 30 Apr 2004 13:34
I got AC with 0.031 373 KB using brute force.
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
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
Posted by Gleb Ovchinnikov 28 Mar 2019 19:39
Hello, explain to me why you use
l:=(l*i) mod m;(...mod m)?!!
Why?