欧几里得算法
文中用 表示求模运算, 表示整除, 比如
欧几里德算法(称辗转相除法),用于计算两个整数a, b的最大公约数gcd(a, b).
基本原理
- 与第3条结合, 可以写更相减损术
- 与第3条结合, 欧几里得算法(辗转相除法)
-
是点集 中最小的正整数.
c/c++ 实现的欧几里得算法
int gcd(a, b)
{
int temp;
while(b)
{
temp = b;
b = a % b;
a = temp;
}
return a;
}
扩展欧几里得算法
求的整数解
因为我不是学数学的, 严谨的证明就不写了. 只写一点简单的推导
递推公式
设
根据上式的 c++ 实现
void exgcd(int a, int b, int& g, int& x, int& y)
{ // 纯c好像不支持引用, 可以用指针代替.
if(!b)
{
g = a;
x = 1;
y = 0;
}
else exgcd(b, a % b, g, x, y);
int t;
t = x;
x = y;
y = t -(a / b) * y;
}
非递归算法
这个稍有些难, 仍然是
step1 .
step2.
step3. if(r==0) 结束, else继续
step4. 去step2
初始时由上step1的定义有
第一次到step3, 如果,就是的解
step4
(1)式变为 , (3)式变为
void exgcd(int a, int b, int& g, int& x, int& y)
{ // 可以用来求逆元
if(!b)
{
x = 0;
y = 1;
g = a;
}
else
{
int x1, y1, q, r, t;
x1 = y = 1; y1 = x = 0;
r = a % b; q = a / b;
while(r)
{
a = b;
b = r;
t = x1;
x1 = x;
x = t - q * x;
t = y1;
y1 = y;
y = t - q * y;
r = a % b;
q = a / b;
}
g = b;
}
}
网友评论