|
|
back to boardShow all messages Hide all messagesI have "Time Limit" in test #4. Can you help me. [code deleted] Edited by moderator 01.06.2006 16:14 Of course you got TLE... you algo is O(n)and certainly will get TLE Real Help! First of all we must diminish number of candidate to optimal. MathHelp:if (A^k)%N==1 => fi(N)%k==0 where fi(N)-Eiler function of N Try find in Internet effective algorith for fi(N). we can see that number of candidates diminished from 1000000000 to 2*sqrt(1000000000)~64000 Also if Nod(A,N)>0 print 0. Final trick is using divide recursion when calculating (A^K)%N=>O(log K)-time and don't forget use __int64 when form A*B Edited by author 17.08.2007 02:26 Good point svr! :) But number of ways diminishes to amount of divisors of phi(N) which is way less than 64000, and it's enough to factorize phi(N) itself to get them all recursively. Edited by author 20.08.2008 17:46 NOD is russian for GCD :-) |
|
|