Number of solutions for the given condition

[liveoverflow]

Given X,p,a,b, we need to find out how many n\in\mathbb N,\;(1\leqslant n\leqslant X)\; satisfy the following condition:

na^n\equiv b\pmod{p}

Constraints:
(1\leqslant X \leqslant 10^{12})\;
(1\leqslant p \leqslant 10^{6})\;
(1\leqslant a,b \leqslant p)\;

I have no idea how to solve this question, any approach or proof will be highly appreciated.

Thank you in advance!

[everule1]

I’m assuming p is prime?

Https://codeforces.com/problemset/problem/919

/* 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 fi…