ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
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.
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
Posted by Gleb Ovchinnikov 28 Mar 2019 19:39
Hello, explain to me why you use
l:=(l*i) mod m;(...mod m)?!!
Why?