文章目录
- 1、给出Bezout定理的完整证明。
- 2、实现GCD算法的迭代版本。
- 3、实现EGCD算法。输入:a、b两个整数,输出:r、s、d三个整数,满足ar + bs =d。
- 4、实现一种批处理版本的GCD算法,即,给定一个整数数组,输出其中所有整数的最大公因子。输入:一个整数数组a;输出:一个整数d,是a数组中所有整数的最大公因子。
1、给出Bezout定理的完整证明。
2、实现GCD算法的迭代版本。
代码如下:
#include<iostream>
using namespacce std;
{
if(a<b)
{
return(b,a);
}
if(b==0)
{
return a;
}
else
{
return gcd(b,a%b);
}
}
int main()
{
int a,b,c=0;
cin>>a>>b;
c=gcd(a,b);
cout<<c<<endl;
return 0;
}
3、实现EGCD算法。输入:a、b两个整数,输出:r、s、d三个整数,满足ar + bs =d。
代码如下:
#include<iostream>
using namespace std;
int egcd(int a, int b, int s0, int s1, int r0, int r1, int q)
{
if (b == 0)
{
cout << a << ' ' << r0 << ' ' << s0;
}
else
{
egcd(b, a % b, r1, r0 - q * r1, s1, s0 - q * s1, a / b);
}
}
int main()
{
int a, b, r0, r1, s0, s1, q;
r0 = 1;
r1 = 0;
s0 = 0;
s1 = 1;
q = 0;
cin >> a >> b;
egcd(a, b, r0, r1, s0, s1, q);
return 0;
}
4、实现一种批处理版本的GCD算法,即,给定一个整数数组,输出其中所有整数的最大公因子。输入:一个整数数组a;输出:一个整数d,是a数组中所有整数的最大公因子。
代码如下:
#include <iostream>
using namespace std;
unsigned int gcd(unsigned int a, unsigned int b)
{
int m, n;
if (a == 0) return b;
if (b == 0) return a;
for (m = 0; 0 == (a & 1); ++m)
{
a >>= 1;
}
for (n = 0; 0 == (b & 1); ++n)
{
b >>= 1;
}
if (n < m)
{
m = n;
}
while (true)
{
if (a < b)
{
a = a ^ b;
b = b ^ a;
a = a ^ b;
}
if (0 == (a -= b))
{
return b << m;
}
while (0 == (a & 1))
{
a >>= 1;
}
}
}
unsigned int main()
{
unsigned int a, b, c = 0;
cin >> a >> b;
c = gcd(a, b);
cout << c << endl;
return 0;
}