P1082 [NOIP2012 提高组] 同余方程

原题链接

扩展欧几里得算法的应用，关于原理性的讲解这里就略去了，这边给出学习链接即模板。

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

文章链接      视频链接

首先原题方程可以化简为 ax=by+1 即 ax-by=1（正负无所谓）；

那么根据裴蜀定理我们可以得到得到该方程的一个特解，该解不一定是题目要求的最小正整数解。

此时我们对x批量的进行b的增减，原因如下：

ax+by=1;

ax+by+k*ab-k*ab=1;

a(x-kb)+b(y+ka)=1;

显然此时x-kb，y+ka仍为整数。

因此为了保证x0为最小整数，我们进行如下操作：

x=（x%b+b）%b

code

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