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 1456. Jedi Riddle 2

TO ADMIN (Problem 1456)
Posted by cash 25 Apr 2006 19:52
I have "Time Limit" in test #4.
Can you help me.

[code deleted]

Edited by moderator 01.06.2006 16:14
Re: TO ADMIN (Problem 1456)
Posted by CO2 26 Apr 2006 08:17
Of course you got TLE...
you algo is O(n)and certainly will get TLE
Re: TO ADMIN (Problem 1456)
Posted by svr 17 Aug 2007 02:25
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
Re: TO ADMIN (Problem 1456)
Posted by Denis Koshman 20 Aug 2008 16:40
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
Re: TO ADMIN (Problem 1456)
Posted by Semm 4 Aug 2016 14:54
NOD is russian for GCD :-)