同余方程

https://ac.nowcoder.com/acm/problem/16563

扩展欧几里得

方程ax+by=n,当n能够被gcd(a,b)整除时，那么就可以用扩展欧几里得来求改方程的特解。

同余方程

同余方程ax≡m(mod b)，意思是ax模b的值等于m模b的值，做下变换有(ax-m)%b≡0,说明(ax-m)是b的整数倍，设该整数为k，那么(ax-m)=kb,即ax-kb=m,因为k可以为正数或负数，所以ax+kb=m,接下来可以用扩展欧几里得来求一个解。

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
const int Max = 100 * 100 * 100 + 5;
#define LL long long
const int mod = 1e9+7;
const int INF = 1e9+7;
//const int inx = INT_MAX; 
using namespace std;
//    srand(time(NULL));
//        m = rand() % 1000 + 1;

//定义i i(A) i+n i+n(B) i+n+n i+n+n(C) 
//bitset<Max>s,q;

LL gcd_ex(LL a,LL b,LL &x, LL &y)//扩展欧几里得
{
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    LL d = gcd_ex(b,a % b,y,x);
    y = y - a / b * x;
    return d;
}

int main()
{
    LL a,b,x,y;
    cin >> a >> b;
    LL t = gcd_ex(a,b,x,y);
    cout << (x + b) % b;
    return 0;
}