知识储备
扩展欧几里得定理
欧几里得定理
(未掌握的话请移步 [扩展欧几里得 https://blog.csdn.net/floatiy/article/details/80452643])
正题
设存在 ax+by=gcd(a,b), 求 x,y.
我们已经知道了用扩欧求解的方法是递归, 终止条件是 x==1,y==0;
- int exgcd( int a, int b, int &x, int &y ) {
- if( b == 0 ) {
- x = 1;
- y = 0;
- return a;
- }
- int tmp = a % b;
- if( tmp> b ) swap( tmp, b );
- int ans=exgcd(b,a%b,x,y);
- tmp = x;
- x = y;
- y = tmp - a / b * y;
- return ans;
- }
到 b==0 时, 我们可以得到一组解:(1,0).
接下来再逐步回带, 求出所有可能的解. 具体是为什么呢?
证明
已知:
- ax1+by1=gcd(a,b)
- bx2+(a mod b)y2=gcd(a,b)
- a mod b = a-a/b*b
可求得:
ax1+by1=bx2+(a mod b)y2=gcd(a,b)
即
ax1+by1=bx2+(a-a/b*b)y2=gcd(a,b)
化简得
ax1+by1=bx2+ay2-a/b*b*y2=gcd(a,b)
所以可证出:
对于每一次递归中的 x1y1, 与上一次递归中的 x2y2 存在如下关系:
x1 = y2,y1 = x2 - a / b * y2
证明毕,
每次的 x 和 y 均存在递归关系, 所以我们可以在求得一组解后回溯时回带求出其他解, 此时计数
P.S.
对于求方程正整数解的个数的题, 需要注意特判
设 ax+by=c, 给定 a,b,c, 求 x,y 的正整数解个数
x=0,y=0,z=0 时, 方程无数解
x=0,y=0,z!=0 时, 方程无解
x,y<0,z>0 时方程无解, 反之亦然
来源: http://www.bubuko.com/infodetail-2723111.html