возможные решения для данного уравнения

Question

Учитывая X, р, а, б. Нам нужно выяснить, сколько натуральных чисел n (1 <= n <= X) удовлетворяет следующему условию: - </p>

na^n ≡ b(mod p)

Constraints:  
2 <= p <= 10^6,  
1 <= a,b< p,  
1 <= X <= 10^12  

Я понятия не имею, как решить этот вопрос, любой подход или доказательство будут очень полезно.

Спасибо.

Answer 1

Предполагается, что p является простым.

Для каждого i от 1 и выше вычисляется a^i. В какой-то момент (назовите это q), вы получите 1, а затем можете остановиться. Затем нахождение всех n <= X таких, что na^n = b (mod p) и a^n = a^i (mod p) - это вопрос подсчета всех решений n = b*(a^i)^-1 (mod p) и n=i (mod q), что вы можете сделать, используя теорему об остатках в Китае.

Этот процесс перечисляет все решения ровно один раз, и, если вы будете осторожны, выполняется за O (p) время. (Необходимо соблюдать осторожность, чтобы избежать O (p log p), если вы вычисляете a^i (mod p) и (a^i)^-1 (mod p) с нуля каждую итерацию).