liveoverflow's blog

By liveoverflow, history, 2 months ago, In English,

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:

$$$\begin{aligned}\begin{equation}2\leqslant p\leqslant 10^6\\1\leqslant a,b\lt p\\1\leqslant X\leqslant 10^{12}\end{equation}\end{aligned}$$$

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

Thank you in advance!

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Only $$$X$$$ is given? What about $$$a$$$ and $$$b$$$ and $$$p$$$? They can be anything?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems related to the discrete logarithm, so start by reading about it.

https://en.wikipedia.org/wiki/Discrete_logarithm