P12540 [XJTUPC 2025] 离散对数 题解

#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;
}