【Codeforces】Round #460 E

题意

求满足$na^nequiv b pmod p$的$n$的个数

---

因为$n mod p ​$循环节为$p​$，$a^nmod p​$循环节为$p-1​$，所以$na^n mod p​$循环节为$p(p-1)​$

假设$n mod p equiv i,a^nmod pequiv a^j$ ， 那么$n%p imes a^n%pequiv b pmod p$，得到$i imes a^j equiv b pmod p$，列同余方程$i equiv b*a^{-j} pmod p, iequiv j pmod {p-1}$，解得$i=(p-1)^2baj+pj$，在$n$的上限内计算答案

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a, b, p, x, ans = 0;
LL quick_pow(LL x, LL y, LL mod) {
    LL ret = 1;
    for(; y; y >>= 1) {
        if(y & 1) ret = (ret * x) % mod;
        x = (x * x) % mod;
    }
    return ret;
}
int main() {
    cin >> a >> b >> p >> x;
    for(LL i = 1; i < p; ++i) {
        LL inv = quick_pow(quick_pow(a, i, p), p - 2, p);
        LL y = b * inv % p;
        LL P = p * (p - 1);
        LL r = (p * i + (p - 1) * (p - 1) % P * y) % P;
        ans += x / P + (x % P >= r);
    }
    cout << ans << endl;
    return 0;
}