P12540 [XJTUPC 2025] 离散对数 题解

HDS_Acenaphthylene · 2025-05-19 09:54:57 · 题解

我是糖比没看出来 b = (p - 1) ^ 2。

给定正整数 a, c, p，保证 p 是 素数，求 b 使得：

显然若 a \equiv b \pmod p, 则:

根据费马小定理,有:

则由二式可得, 若

则

显然是个 ExCRT 板子。

#include<bits/stdc++.h>
using namespace std;
#define int long long
std::ostream& operator << (std::ostream &out,__int128 a){
    if(a<0)out<<'-',a=-a;
    if(a>9)out<<a/10;
    return out<<(int)(a%10);
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
__int128 exgcd(__int128 a, __int128 b, __int128 &x, __int128 &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    __int128 ret = exgcd(b, a % b, x, y);
    __int128 t = x;
    x = y;
    y = t - (a / b) * y;
    return ret;
}
struct equ{
    __int128 a, mod;
    equ operator +(equ b) {
        __int128 k1, k2;
        /*
        x = r1 mod m1  x = k1m1 + r1
        x = r2 mod m2  x = k2m2 + r2
        k1m1 - k2m2 = r2 - r1
        */
        __int128 _m = mod / gcd(mod, b.mod) * b.mod;
        exgcd(mod, b.mod, k1, k2);
        k1 = (k1 + _m) % _m;
        k1 = ((b.a - a) / gcd(mod, b.mod) + _m) % _m * k1 % _m;
        __int128 _r = (k1 * mod + a) % _m ;
        return {_r, _m};
    }
};
signed main() {
    long long a;
    cin >> a;
    equ now;
    long long md, c;
    cin >> c >> md;
    now = {a, md};
    now = now + (equ){c, md - 1};
    cout << now.a;
    return 0;
}