[NOIP2012 提高组] 同余方程
题目描述
求关于 $ x$ 的同余方程 $ a x \equiv 1 \pmod {b}$ 的最小正整数解。
输入格式
一行，包含两个整数 $a,b$，用一个空格隔开。
输出格式
一个整数 $x_0$，即最小正整数解。输入数据保证一定有解。
样例 #1
样例输入 #1
3 10样例输出 #1
7提示
数据规模与约定
- 对于 $40\%$ 的数据，$2 ≤b≤ 1,000$；
- 对于 $60\%$ 的数据，$2 ≤b≤ 50,000,000$；
- 对于 $100\%$ 的数据，$2 ≤a, b≤ 2,000,000,000$。
题目分析
分析1
若对数论足够熟悉，可一眼看出本题要求的是a在模b意义下的逆元。简单回顾下逆元。
逆元在不同计算规则下表现出的内容是 不一样的。
在加法计算规则下，$0+x=x+0=x$，$0$与其他元素结合时，并不会改变那些元素，我们称$0$是加法计算规则下的单位元。而$x + (-x)=0$，对于整数$x$来说，加上相反数$-x$等于单位元，我们称 $(-x)$为$x$在加法规则下的逆元。
在乘法计算规则下，$1 \times x=x \times 1=x$，$1$与其他元素结合时，并不会改变那些元素，我们称$1$是乘法计算规则下的单位元。而$x\times \frac{1}{x}=1$,对于整数$x$来说，乘上倒数$\frac{1}{x}$或者$x^{-1}$ 等于单位元，我们称 $x^{-1}$为$x$在乘法规则下的逆元。
总结下单位元与逆元的定义，在某种计算规则下，某元素$e$与任意元素$a$结合运算得到元素$a$，则称$e$这个运算下的单位元。如果任意两个元素的运算结构等于单位元，则称这两个元素互为逆元。
我们拓展到乘法取模的计算规则。
在该计算规则下，若$a \mod m=b\mod m$ 则称$a,b$在模$m$下同余，也写为$a\equiv b(\mod m) $。此时，$x\times 1 \mod m=1\times x \mod m$，所以$1$是乘法取模意义下的单位元。若$a\cdot x\mod m=1\mod m$，也就是$a\cdot x\equiv 1(\mod m)$,也就是$x$为$a$的逆元。
因为本题的模数m不保证为质数，所以采用扩展欧几里德的方法进行求解。这是直接通过对逆元知识点的熟悉所推出的内容。
分析2
也可以从本题的内容出发，进行推导。
因为 $ax\equiv 1 (\mod m)$ 所以$ax-1\equiv 0 (\mod m)$，也就是说$m|(ax-1)$。
也就是存在整数$k$使得$mk=ax-1$,移项之后可得到$ax+m\cdot(-k)=1$ 符合贝祖等式$ax+by=d$的形式。
题目保证数据一定有解，所以相当于求$ax+my=1$的x的最小正整数解。
可以利用扩展欧几里德算法求出该等式的一组特解，再处理一下$(x+m)\%m$求出最小正整数解极了。
扩展欧几里德
设$d=gcd(a,b)$
根据裴蜀定理可得到等式(贝祖等式):$ax+by=d$
令$a\div b=\lfloor\frac{a}{b}\rfloor\cdots r$ ,故$r=a-\lfloor\frac{a}{b}\rfloor\cdot b$
根据欧几里得算法，$gcd(a,b)=gcd(b,a\%b)=gcd(b,r)=d$
当$b=0$，可得到一组特殊解：$x=1,y=0$
当$b\neq 0$，根据裴蜀定理：
$bx'+ry'=d$
$=bx'+(a-\lfloor\frac{a}{b}\rfloor\cdot b)y'=d$
$=bx'+ay'-b\cdot\lfloor\frac{a}{b}\rfloor y'=d$
$=ay'+b(x'-\lfloor\frac{a}{b}\rfloor y')=d$
$\because$
$$ \left\{\begin{aligned} ay'+b(x'-\lfloor\frac{a}{b}\rfloor y')=d\\ ax+by=d \end{aligned}\right. $$
$\therefore$
$$ \left\{\begin{aligned} x&=y' \\ y&=x'-\lfloor\frac{a}{b}\rfloor y' \end{aligned}\right. $$
即可发现x,y更新规律。
扩展欧几里得算法代码实现
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int z=x;x=y;y=z-y*(a/b);
return d;
}代码实现
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;y=0;
return a;
}
ll d = exgcd(b,a%b,x,y);
ll z=x;x=y;y=z-y*(a/b);
return d;
}
int main(){
ll x,y;
ll a,b;
cin>>a>>b;
exgcd(a,b,x,y);
cout<<(x%b+b)%b;//求最小正整数解
return 0;
}