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

a idea
Posted by HaiyangZheng 8 Oct 2012 12:13
since X,M,Y in [0,1000]... power(X,N) is very large, we can't to calculate!

f(N) = X^N mod M = Y

then, X^N=k*M+Y

f(N+1) = X^(N+1) mod M
           = (X^N*X) mod M
           =(k*M*X+Y*X) mod M
           =Y*X mod M
           =f(N)*X mod M

example for X,M,Y is 2,6,4.
f(0)=2^0 mod 6    = 1
f(1)=f(0)*2 mod 6 = 2
f(2)=f(1)*2 mod 6 = 4 (ok)
f(3)=f(2)*2 mod 6 = 2
f(4)=f(3)*2 mod 6 = 4 (ok)
f(5)=f(4)*2 mod 6 = 2
f(6)=f(4)*2 mod 6 = 4 (ok)

thanks.
Re: a idea
Posted by iLko 3 Dec 2012 02:00
an idea !
Re: a idea
Posted by aybek [UrTICCS] 13 Jan 2014 21:50
thanks for idea!
But there is a mistake. Input format is N, M, Y.
It seems that it is DP problem.
So, you must define recursive function
f(x, n, m) = {
    1%m                 | if n is 0
    f(x, n-1, m)*x % m  | else
}
And call it
for every x from 0 to m-1.
Algorithm complexity is O(n^2)
So, at worst case there will be at about 1 000 000 iterations.
But it works. Thanks for idea! Good luck ;)