G18 同余方程 乘法逆元 扩展欧几里得算法

#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, y, x);
        y-=(a/b)*x;
    }
}
int main()
{
    LL a, b, m;scanf("%lld%lld%lld", &a, &b, &m);
    LL A, B, d, X, Y, K;
    A=a, B=m, K=b;
    exgcd(A, B, d, X, Y);
    if(K%d!=0) printf("no solution!\n");
    else
    {
        LL dx=abs(B/d), dy=abs(A/d);
        X=X*(K/d);
        X=( X%dx + dx ) %dx;
        printf("%lld\n", X);
    }
    return 0;
}