题目链接：
http://codeforces.com/problemset/problem/919/E
题意：
让你求满足 \(na^n\equiv b \pmod p\) 的 \(n\) 的个数。
\(2 ≤ p ≤ 10^{6} + 3, 1 ≤ a, b < p, 1 ≤ x ≤ 10^{12}\).
题解：
因为：
$n \mod p $的循环节是 \(p\)
\(a^{n} \mod p\)的循环节是 \(p-1\)。(费马小定理)
所以： \(na^n \mod p\)的循环节为 \(p*(p-1)\)。
因为 \(p\)是质数。
假设: \(n \mod p \equiv i, a^n\mod p\equiv a^j\).
\(a^n \mod p \equiv i\) ----①
$a^n\mod p\equiv a^j $ ----②
\(na^n\equiv b \pmod p\) ----③
可以得到： \(i \times a^j \equiv b \pmod p\).
我们现在枚举的\(a^n\) 中的 \(n\) 为 \(j\) , 满足 \(n \times a^n\ mod\ p\ = \ b\) 的 \(n\) 为 \(i\).
列出同余方程：
$i \equiv b*a^{-j} \pmod p $ ---①
\(i\equiv j \pmod {p-1}\) ---②
利用 \(CRT\) 可以解出 ：\(i=(p-1)^2ba^{-j}+pj\) ，其中 \(a^{-j}\) 是$ a^{j}$ 在 $\mod p $意义下的逆元。
因为在所有 \(<=x\) 的 \(i\) 的倍数都满足条件，除法统计一下即可。
复杂度：\(O(p*logp)\)
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpower(ll a,ll b, ll mod)
{
ll ans = 1;
while(b){
if(b&1) ans = ans * a % mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
ll a,b,mod,x;
int main(int argc, char const *argv[]) {
std::cin >> a >> b >> mod >> x;
ll ans = 0;
for(int i = 1;i <= mod-1;i++) {
ll c = qpower( qpower(a, i , mod) , mod - 2, mod) * b % mod;
ll n = ((mod-1) * (mod-1) * c + mod * i) % (mod * (mod-1));
ans += ( x / (mod * (mod-1)) ) + (x % (mod * (mod-1)) >= n );
}
std::cout << ans << '\n';
return 0;
}
转载于:https://www.cnblogs.com/LzyRapx/p/8405402.html
相关资源：各显卡算力对照表！
