关于拓展欧几里德的一道题

题目来源：

http://139.224.237.251:23333/problem/3003

题目描述：

题解:

exgcd
推公式部分略。注意 c == 1 的情况和爆 ll 的情况。
爆 ll 的解决方法:
1,int128(我的电脑用不了
2, 快速乘(推荐)

参考代码：

//http://139.224.237.251:23333/problem/3003
//ax-kc=1-b(k为非负整数)
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define end '\n'
#define IOS ios::sync_with_stdio(0)

ll q_mul(ll a,ll b,ll mod){
    ll ans = 0;
    while (b) {
        if (b & 1) {
            ans = (ans + a)%mod;
        }
        a = (a + a)%mod;
        b >>= 1;
    }
    return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    ll r = exgcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * y;
    return r;
}

int main() {
    IOS;
    ll a, b, c;
    while (cin >> a >> b >> c) {
        b = ((1 - b) % c + c) % c;
        ll gcd, x, y;
        gcd = exgcd(a, c, x, y);
        if (b % gcd || c == 1) {
            cout << "God plz" << end;
            continue;
        }

        ll t = c / gcd;
        cout << (q_mul((t + x % t) % t, b / gcd, t)%t+t)%t<< end;
    }
    return 0;
}