给定方程的可能解
possible solutions for the given equation
给定 X,p,a,b。我们需要找出有多少个正整数 n ( 1 <= n <= X) 满足以下条件：-
na^n ≡ b(mod p)
Constraints:
2 <= p <= 10^6,
1 <= a,b< p,
1 <= X <= 10^12
我不知道如何解决这个问题，任何方法或证明都会很有帮助。
谢谢。
这假设 p 是素数。
对于从 1 开始的每个 i，计算 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) 时间内运行。 （如果每次迭代从头开始计算 a^i (mod p) 和 (a^i)^-1 (mod p)，需要注意避免 O(p log p)。
给定 X,p,a,b。我们需要找出有多少个正整数 n ( 1 <= n <= X) 满足以下条件：-
na^n ≡ b(mod p)
Constraints:
2 <= p <= 10^6,
1 <= a,b< p,
1 <= X <= 10^12
我不知道如何解决这个问题，任何方法或证明都会很有帮助。
谢谢。
这假设 p 是素数。
对于从 1 开始的每个 i，计算 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) 时间内运行。 （如果每次迭代从头开始计算 a^i (mod p) 和 (a^i)^-1 (mod p)，需要注意避免 O(p log p)。