#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
 
void exgcd(LL a, LL b, LL &d, LL &x, LL &y) {
    if (b == 0) {
		d = a;
		x = 1;
		y = 0;
	}
    else {
        exgcd(b, a % b, d, x, y);
        int t = x;
        x = y;
        y = (t - (a / b) * y);
        /*
        嫌麻烦也可以这么写，传进去的位置无所谓的，反正都没实值 
        exgcd(b, a % b, d, y, x);
        y -= (a / b) * x;
        */
    }
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
    LL a, b, m;
    cin >> a >> b >> m;
    LL A, B, d, X, Y, K;
	A = a, B = m, K = b;
	
	exgcd(A, B, d, X, Y);   // d, X, Y 并没有实值，是传引用进去 
	
    if (K % d != 0) {
		cout << "no solution!\n";
	}
	
    else {
    	LL dx = abs(B / d), dy = abs(A / d);
    	X = X * (K / d);
        X = ( X % dx + dx ) % dx;
        cout << X << "\n";
    }
    return 0;
}

https://blog.csdn.net/tenkuo/article/details/149441606

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
void exgcd(LL a, LL b, LL &d, LL &x, LL &y)
{
    if(a == 0) { d = b; x = 0; y = 1; }
    else
    {
        LL tx, ty; exgcd(b % a, a, d, tx, ty);
        x = ty - (b / a) * tx;
        y = tx;
    }
}
int main()
{
    LL a, b, x, y, d;
    cin >> a >> b;
    exgcd(a, b, d, x, y);
    x = ((x % b) + b) % b;
    cout << x << endl;
    return 0;
}