首页 > 编程语言 > 详细

整数性质(拓展欧几里得算法)

时间:2018-06-18 21:34:43      阅读:243      评论:0      收藏:0      [点我收藏+]

整数性质

时间限制:500 ms  |  内存限制:65535 KB
难度:1
 
描述

我们知道,在数学中,对于任意两个正整数a和b,必定存在一对整数s、t使得sa+tb=gcd(a,b)。

 
输入
多组测试数据。
每组数据输入两个非负整数a和b且a+b>0且a不等于b。
其中0<=a,b<100000。
输出
输出满足条件的 s 和 t 。
样例输入
2 4
3 8
737 635
样例输出
1 0
3 -1
193 -224
 1 /*
 2 扩展欧几里德定理
 3 
 4 对于与不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数。那么存在唯一的整
 5 数 x,y 使得 gcd(a,b)=ax+by。
 6 设 a>b。
 7 1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;
 8 2,ab<>0 时
 9 设 ax1+by1=gcd(a,b);
10 bx2+(a mod b)y2=gcd(b,a mod b);
11 根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
12 则:ax1+by1=bx2+(a mod b)y2;
13 即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
14 根据恒等定理得:x1=y2; y1=x2-(a/b)*y2;
15 这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.
16 上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以
17 结束。
18 */
19 #include<stdio.h>
20 int s,t;
21 void f(int a,int b)
22 {
23     int k;
24     if(a==0){
25         s=0;
26         t=1;
27         return;
28     }
29     else if(b==0){
30         s=1;
31         t=0;
32         return;
33     }
34     else{
35         f(b,a%b);
36         k=s;
37         s=t;
38         t=k-a/b*t;
39     }
40 }
41 int main()
42 {
43     int a,b;
44     while(scanf("%d%d",&a,&b)!=EOF){
45         f(a,b);
46         printf("%d %d\n",s,t);
47     }
48     return 0;
49 }

解题思路:(转载http://www.cnblogs.com/zyf0163/p/4792953.html)

相信大家对欧几里得算法,即辗转相除法不陌生吧。

代码如下:

 
int gcd(int a, int b){
    return !b ? gcd(b, a % b) : a;
}

而扩展欧几里得算法,顾名思义就是对欧几里得算法的扩展。

切入正题:

首先我们来看一个问题:

求整数x, y使得ax + by = 1, 如果gcd(a, b) != 1, 我们很容易发现原方程是无解的。则方程ax + by = 1有正整数对解(x, y)的必要条件是gcd(a, b) = 1,即a, b 互质。

此时正整数对解(x, y)可以通过扩展欧几里得算法求得。

对于方程ax + by = gcd(a, b);我们设解为x1,  y1

我们令a = b, b = a % b;

得到方程bx + a % by = gcd(b, a % b);

由欧几里得算法可以得到gcd(a, b) = gcd(b, a % b);

代入可得:bx + a % b y = gcd(a, b)

设此方程解为x2, y2

在计算机中我们知道: a % b = a - (a / b) * b;

代入方程化解得:

ay2 + b(x2 - (a / b) y2) = gcd(a, b);

与ax1 + by= gcd(a, b) 联立,我们很容易得:

x1 = y2, y1 = x- (a / b)y2;

然后我们就这样可以解出来了。

等等我们似乎忘记一个东西了吧?对就是递归的终点。也就是最后方程的解x和y。

对于方程ay2 + b(x2 - (a / b) y2) = gcd(a, b);

当b = 0时,发现a * 1 + b * 0 = gcd(a, b)

则有x = 1, y = 0。

由此我们把ax + by = 1的其中一组解解出来了, 仅仅是其中一组解。

对于已经得到的解x1, y1;我们便可以求出通解。

我们设x = x1 + kt;t为整数

带入方程解得y = y1 - a * k / b * t;

而我们要保证y也为整数的话必须保证a * k /b也为整数,我们不妨令k = b/gcd(a, b);

所以通解为:

x = x1 + b / gcd(a, b) * t;

y = y1 -  a / gcd(a, b) * t;

其中t为整数。

附上伪代码:

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

整数性质(拓展欧几里得算法)

原文:https://www.cnblogs.com/geziyu/p/9196133.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!