基础数论题,费马小定理+逆元

题意

求有多少个 n(1nx)n (1 \leq n \leq x) 满足 nanb(modp)na^n \equiv b \pmod{p} ,其中 pp 为质数。

输入给定 a,b,p,x(2p106,1x1012,1a,b<p)a, b, p, x(2 \leq p \leq 10^6, 1 \leq x \leq 10^{12}, 1 \leq a,b < p)

题解

首先,由费马小定理可以推出以下公式:

ananmodp1(modp)a^n \equiv a^{n \bmod{p-1}} \pmod{p}

  1. n<p1n < p-1 时,an=anmodp1a^n = a^{n \bmod{p-1}}

  2. n=k(p1)n = k(p-1) 时,nmodp1=0n \bmod{p-1} = 0,则 anmodp1=a0=1a^{n \bmod{p-1}} = a^0 = 1

  3. 剩下情况可以用数学归纳法推出来

那么设:

n=k(p1)+t(0tp1)n = k(p-1) + t \quad (0 \leq t \leq p-1)

代入原式:

nanb(modp)(k(p1)+t)ak(p1)+tb(modp)k(p1)+tbat(modp)k(batt)(p1)1(modp)na^n \equiv b \pmod{p} \\ (k(p-1)+t)a^{k(p-1)+t} \equiv b \pmod{p} \\ k(p-1) + t \equiv ba^{-t} \pmod{p} \\ k \equiv (ba^{-t} -t)(p-1)^{-1} \pmod{p}

由于 tp1,p[2,106]t \leq p-1, p \in [2, 10^6],故可以通过枚举 tt 来计算 kk

设求出来的值为 k0[0,p)k_0 \in [0,p)kk0(modp)k \equiv k_0 \pmod{p}

那么 k=mp+k0k = m \cdot p + k_0

最后我们只需要算出对于每个 tt,有多少个 m0m \geq 0 使得原式成立

n=(mp+k0)(p1)+t=mp(p1)+k0(p1)+txm=xk0(p1)tp(p1)n = (mp+k_0)(p-1) + t = mp(p-1) + k_0(p-1) + t \leq x \\ m = \frac{x-k_0(p-1)-t}{p(p-1)}

代码实现

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

ll fpm(ll a, ll b, ll mod) {
    ll res = 1, temp = a;
    for (; b; b = b >> 1) {
        if (b & 1) {
            res = res * temp % mod;
        }
        temp = temp * temp % mod;
    }
    return res;
}


ll a,b,p,x;
int main() {
    cin >> a >> b >> p >> x;

    // 求p-1在模p意义下的逆元
    ll invP = fpm(p-1, p-2, p);

    ll ans = 0;
    // 枚举t来计算k
    for(int t = 0; t < p-1; t++) {
        ll invA = fpm(fpm(a,t,p), p-2, p);
        ll k = (b * invA - t) * invP % p;
        k = (k + p) % p;
        ll d = x - k * (p - 1) - t;
        if(d >= 0) {
            ans += d / (p * (p - 1)) + 1;
        }
    }

    cout << ans << endl;
    return 0;
}