|
|
back to boarda idea 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 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 ;) |
|
|