【厦门大学“网宿杯“17届程序设计竞赛决赛】D-财富密码

财富密码

https://ac.nowcoder.com/acm/contest/5945/D

题意：

给定 $a, b, p, x$ ，其中 $2 \leq p \leq 10^6, 1 \leq x \leq 10^{12}, 1 \leq a, b < p$ 。
求有多个 $n$ ，满足 $1 \leq n \leq x，n a^n \equiv b \space (mod \space p)$ 。

题解：

需要一些简单的数论知识：

费马小定理：若 $p$ 为质数，而整数 $a$ 不是 $p$ 的倍数，则 $a^{p-1} \equiv 1 \space (mod \space p)$ 。
逆元：定义整数 $a$ 在模 $p$ 意义下的逆元为 $x$ ，则 $ax \equiv 1 \space (mod \space p)$ ，可记作 $x \equiv a^{-1} \space (mod \space p)$ 。
在 $1$ 条件下，有 $x \equiv a^{p - 2} \space (mod \space p)$ 。因为 $ax \equiv a \times a^{p-2} \equiv a^{p-1} \equiv 1 \space (mod \space p)$ 。

然后到这道题：
首先由费马小定理可以得到 $a^n \equiv a^{n \space mod \space (p - 1)} \space (mod \space p)$ ，
因此可以设 $n = k(p - 1) + t, (0 \leq t \le p - 1)$ 。
然后推式子：

$(k(p-1)+t)a^{k(p-1)+t} \equiv b \space (mod \space p)$
$(k(p-1)+t)a^{t} \equiv b \space (mod \space p)$
$k(p-1)+t \equiv b a^{-t} \space (mod \space p)$
$k \equiv (ba^{-t} - t) (p-1)^{-1} \space (mod \space p)$

由于 $t \leq p - 1$ ， $p$ 范围为 $10^6$ 。故可以枚举 $t$ ，通过上式计算 $k$ 。
需要用到快速幂，一次计算的复杂度在 $log$ 级别。整体估计复杂度是可以通过的。

在已知 $t$ 的情况下，我们根据这个式子可以求出一个 $k_0 \in [0, p)$ ，
显然任意 $k \equiv k_0 \space (mod \space p)$ ，
即 $k = m \times p + k_0$ ，
都有： $n = k(p - 1) + t$ 时 $na^n \equiv b \space (mod \space p)$ 。

$n$ 有限制条件： $1 \leq n \leq x$ 。
对于一个确定的 $t$ ，我们要求的就是有多少个整数 $m \geq 0$ ，使得 $n$ 在范围之内。

$n = (m p + k_0)(p-1) + t = mp(p-1)+ k_0(p-1)+t \leq x$

$m \leq \frac {x - k_0(p-1) - t} {p(p-1)}$

然后在范围内的计入答案就可以了。

Code：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a, b, p;
ll x;
int qpow(int x, int n) {
    assert(n >= 0);
    int res = 1;
    while(n) {
        if(n & 1) res = 1ll * res * x % p;
        x = 1ll * x * x % p;
        n >>= 1;
    }
    return res;
}
int inv(int x) { return qpow(x, p - 2); }
int main() {
    cin >> a >> b >> p >> x;
    ll ans = 0;
    int inv1 = inv(p - 1);
    for(int t = 0; t < p - 1; t++) {
        int k = (1ll * b * inv(qpow(a, t)) - t) * inv1 % p;
        k = (k + p) % p;
        ll d = x - 1ll * k * (p - 1) - t;
        if(d >= 0) ans += d / (1ll * p * (p - 1)) + 1;
    }
    cout << ans << endl;
}