「CodeForces-919E」Congruence Equation(费马小定理)

发表于 | 分类于 ，

「CodeForces-919E」Congruence Equation

给定a,b,n,p，求关于n的方程n⋅a^n≡b(mod p)在[1,x]中整数解的数量

题解

对原式$k \cdot a^k \equiv b \quad (\textrm{mod};p)$，考虑消去指数。由费马小定理，对质数$p$，有$a^{(p-1)} \equiv 1 \quad (\textrm{mod};p)$。

令$k=x\cdot(p-1)+y$，则原式转化为

$$(x\cdot(p-1)+y)\cdot a^{x\cdot(p-1)+y} \equiv b \quad (\textrm{mod};p)$$

$$(x\cdot(p-1)+y)\cdot a^{y} \equiv b \quad (\textrm{mod};p)$$

$$x\cdot(p-1)+y \equiv b \cdot a^{-y}\quad (\textrm{mod}\ p)$$

$$x\equiv y-b \cdot a^{-y}\quad (\textrm{mod}\ p)$$

问题转化为求$x\equiv y-b \cdot a^{-y}\quad (\textrm{mod}\ p)$在$(x\cdot(p-1)+y)∈[1,n]$中解的个数。

枚举$y∈[0,p-2]$，计算$x$的个数，其中若$x,y$均为0时$n=0$，需要减去。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a, b, n, p;

ll inv(ll a, ll n = p - 2)
{
    ll res = 1;
    for(; n; n >>= 1, (a *= a) %= p) if(n & 1) (res *= a) %= p;
    return res;
}

int main()
{
    cin >> a >> b >> p >> n;
    ll inva = inv(a), res = 0;
    for(int y = 0; y < p - 1; y ++)
    {
        // x = y - b * a ^ (-y) + k * p
        ll x = (y - b + p) % p;
        if(y <= n && (n - y) / (p - 1) >= x)
        {
            res += ((n - y) / (p - 1) - x) / p + 1;
            if(x == 0 && y == 0) res --;
        }
        (b *= inva) %= p;
    }
    cout << res << endl;
    return 0;
}