CF 919E Congruence Equation

题目描述

http://codeforces.com/problemset/problem/919/E

简要题意：给定整数 $x,a,b,p$，求有多少正整数 $n$，满足 $na^n\equiv b(\bmod p)$

$2\le p\le 10^6+3,1\le a,b<p,1\le x\le10^{12}$，保证 $p$ 是素数

Solution

$na^n\equiv b(\bmod p)$，对于 $a^n$ 我们知道循环节肯定是 $\varphi(p)$，这里保证 $p$ 是素数，有 $\varphi(p)=p-1$

对于 $n$，它的循环节显然是 $p$，那么我们知道 $na^n$ 的循环节就是 $p(p-1)$是，所以我们只需要求 $p(p-1)$ 内有多少合法的 $n$ 即可

我们令 $n=k(p-1)+r,k\in[0,p-1],r\in[0,p-1]$

那么 $na^n\equiv b(\bmod p)$ 可以得到 $k\equiv r-ba^{-r}(\bmod p)$，我们枚举 $r$，可以得到给定范围的 $k$，进而得到 $n$​

#include <iostream>
#define ll long long
using namespace std;

int p;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

int a, b;

ll n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> a >> b >> p >> n;
    ll ans = 0; 
    for (int i = 0; i < p - 1; ++i) {
        ll k = ((i - b * pow_mod(pow_mod(a, i), p - 2)) % p + p) % p;
        ll x = k * (p - 1) + i;
        if (x > n) continue;
        ans += (n - x) / (1ll * p * (p - 1)) + 1; 
    } cout << ans << "\n"; 
    return 0; 
}