题解 | #【模板】同余方程#

简单的模板题。利用扩展欧几里得即可求。

首先，你要知道在初等数论里，我们把a和b的最大公约数记错记作(a,b)，把b可被a整除记作a|b,把b不可被a整除记作a∤b

扩展欧几里得的证明需要用翡蜀定理

对任意的正整数a b，必然存在x y，使得ax+by=(a,b)

1. 若b=0，那么（a,b）=a。此时定理显然成立
2. 若（a，b）!=0,那么将ax+by=(x,y)转换成证bx+(a%b)y=(b,a%b)，由欧几里得算法得知该式最终会将b变成0，即变成第一步，得证。

当b=0的时候，我们可以看出x=1，y=0必然是个满足的解，那么我们可以通过反递推得到最终的x，y的值。

那么假设原先x，y值为x1与y1，变化后的x，y值为x2，y2。

即得到

ax1+by1=bx2+(b%a)y2(数学语言表达) => ax1+by1=bx2+(b-b/a*a)y2（计算机语言）

展开后我们就可观查得到一个可行解为 x1=y2,y1=x1-[a/b]*y2;

那么我们就可以写出扩展欧几里得的代码

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

得到的x，y就是方程的一个解 但是我们还要求方程的最小正整数解

这就要用到另外一个知识点了，x=x+b/gcd*k的方程的通用解 那么

只要对x取模就能得到最大答案了 附上代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll exgcd(ll a,ll b,ll& x,ll& y)
{
    if(!b)
    {
        x=1;y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    ll T,a,b;
    cin >> T;
    while(T--)
    {
        cin >> a >> b;
        if(__gcd(a,b)!=1)
            cout << -1 << endl;
        else
        {
            ll x,y;
            ll gcd=exgcd(a,b,x,y);
            ll tt=b/gcd;
            cout << (x%tt+tt)%tt << endl;
        }
    }
}