Can anyone help me in solving in this question? I am unable to understand the codeforces editorial. Brute force approach fails as the size of problem is 10^12(max)
/* I have only read the question, I’m not sure */
It is given a and p are coprime. That implies a^{p-1}\equiv1\ mod \ p.
Iterate through all i such that i<p-1. Now find modulo inverse of a^i\ mod\ p. This can be done in O(1), if you exponentiate a^{-1} directly. Now find ba^{-i}.Now n has to ba^{-i}\ mod\ p and i \ mod\ p-1 for this case. That implies n has to be a number such that n=px + ba^{-i}= (p-1)y + i for some integer x \ and\ y. One solution is x=y=i-ba^{-i}. Substitute this to find n\ mod
\ p(p-1). Now count the number of occurences of this remainder in x.
actually the same problem is asked in the today’s gfg contest…
Yes. But they didn’t state that p is prime.
Input
The only line contains four integers a,b,p,x (2≤p≤10^6+3, 1≤a,b<p, 1≤x≤10^{12}). It is guaranteed that p is a prime.
I meant for the gfg problem.
yes , but after compairing gfg editorial with codeforces there is no change at all…
Learn chinese remainder theorem for solving this question 
I know Chinese remainder theorem. However i am not getting how that can be applied to this question. Any hints would be appreciated.
why looping till p is enough?
Looping should be for p(p-1).
I found this code but unable to understand the logic inside condition(a,b,p,x) function. Anyone explanation would be appreciated? Where does chinese remainder theorem used in this?
It’s the same as my solution.
def condition(a, b, p, x):
ans = 0
for i in range(1, p)://0 to p-1 is the same as 1 to p
now = b*inv(pow(a,i,p), p)%p//ba^-i
first = (p-1)*((i-now+p)%p)+i//x=y= i - ba^-1, n=px + ba^-i = (p-1)y + i
if first > x:
continue
ans += (x-first) // (p*(p-1))+1//count occureces of this mod p(p-1)
return ans
1 Like
Could you please explain this code? What concept is this? This is not Chinese remainder theorem. We are using Fermat’s little theorem and optimised (O(logn)) power function. All these things i know. I am badly stuck in that condition function. What is that algorithm? Please mention so that i can learn. If it is a modified form of Chinese remainder theorem or any other adhoc logic, please explain the code 
Why are we iterating till (p-1)?
We know that a^n \ mod \ p is periodic with period p-1. So we iterate over all possible n\ mod\ p-1. Let’s call that i.
Now we want na^n\ \equiv b\ mod\ p, where n\equiv i\ mod\ p-1.Therefore, it is equivalent to finding n such that, na^i\equiv b\ mod\ p.
That implies n\equiv ba^{-i}\ mod\ p.Since n is also i\ mod\ p-1 ,
n=px + ba^{-i}=(p-1)y+i.
One possible case is x=y=i-ba^{-i}.
We are using a bit of chinese remainder theorem to prove that if we know n\ mod\ p and n \ mod\ p-1, There is only one valid n\ mod\ p(p-1), since p and p-1 are always coprime.
So if we substitute x and y, We will get a valid n\ mod\ p(p-1).
Then we count the occurences of n\ mod\ p(p-1) in range x. We do this for all i and add up the answers.
1 Like
How can you say that n≡i mod p−1 ?
We iterate over all i from 1 to p-1., and n must be something mod p-1.
1 Like
I understood that a^n mod p is periodic with period p-1. But is this a property that
a^i mod p is same as a^n mod p where 1<=i<=p-1?