P1082 同余方程

· · 题解

一道数论题。

转化一下题面：

ax \equiv 1 (mod \ b) \Leftrightarrow ax+by=1

联想到扩展欧几里得：

ax+by=\gcd(a,b)

对于形如 ax+by=c 的方程有整数解的条件是c(mod\ \gcd(a,b)) \equiv0

c=1$时若上式成立，则必然有$ \gcd(a,b)=1

题目保证方程有解，所以本题就是一道裸的扩展欧几里得啦。

有一个小小的坑点。题目要求的是输出最小整数解，通过拓展欧几里得得出的答案可能不是最小解，也有可能是负数解。答案需要小小的处理一下。

本题AC代码：

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

注：扩展欧几里得算法模板

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