EXGCD - NOIP 2012 同余方程 - AcWing 203

EXGCD - NOIP 2012 同余方程 - AcWing 203

求关于x的同余方程 ax ≡ 1(mod b) 的最小正整数解。

输入格式

输入只有一行，包含两个正整数a,b,用一个空格隔开。

输出格式

输出只有一行,包含一个正整数x，表示最小正整数解。

输入数据保证一定有解。

数据范围

$2≤a,b≤2?10^9$

输入样例：

3 10

输出样例：

7

分析：

$ax ≡ 1(mod \ b)\quad<=>\quad ax+by=1，y∈Z。$

$数据保证有解，则必有gcd(a,b)=1，$

$否则ax+by=1左右同除gcd(a,b)发现等式右侧不是整数，产生矛盾。$

$解得x=x_0+k\frac{b}{gcd(a,b)}=x_0+b，则x的最小正整数解为x对b取模后的最小正整数。$

代码：

#include<iostream>using namespace std;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;
}int main()
{int a,b,x,y;cin>>a>>b;exgcd(a,b,x,y);cout<<(x%b+b)%b<<endl;return 0;
}