【题解】洛谷P1082 [NOIP2012]同余方程(扩展欧几里得算法详解)

题目

洛谷P1082同余方程

题解

定义gcd(a,b)为a,b的最大公约数(Greatest Common Divisor)。

由欧几里得定理得:

特别地:gcd(a,0)=a

由裴蜀定理得:

扩展欧几里得算法:假设a*x+b*y=gcd(a,b)

1.b=0时,gcd(a,b)=a,解得x=1,y=0

2.b!=0时,假设

可等价变形为:

与方程a*x+b*y=gcd(a,b)比较得:x=y’,y=x’-(a/b)*y’,不断重复操作,递归改变x,y即可求出一组特解x0,y0。

扩展(本文不作证明):令d=gcd(a,b),对于更一般的方程a*x+b*y=c,当且仅当d|c时有解。假设根据a*x+b*y=d求出的一组特解为x0,y0,将方程两边同乘(c/d),就得到了原方程的一组特解(c/d)x0,(c/d)y0,原方程的通解为:

本题解法:题中所给的同余方程等价于a*x+b*y=1(y为整数),此题保证有解,因此gcd(a,b)|1,即gcd(a,b)=1。用扩展欧几里得算法求出特解x0,y0,x的通解为x=x0+k*b(k为整数)。注意题中要求最小正整数解。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月22日 下午10:46

“数学是[计算机]的奴仆。”