1、给出Bezout定理的完整证明。
2、实现GCD算法的迭代版本。
3、实现EGCD算法。输入：a、b两个整数，输出：r、s、d三个整数，满足ar + bs =d。
4、实现一种批处理版本的GCD算法，即，给定一个整数数组，输出其中所有整数的最大公因子。输入：一个整数数组a；输出：一个整数d，是a数组中所有整数的最大公因子。
1、给出Bezout定理的完整证明。
①、
设gcd(a,b)=d，则有k1d=a，k2d=b，k1、k2∈Z+。
故a和b的线性组合am+bn=k1dm+k2dn=d(k1m+k2n)，
明显的，a和b的线性组合总是d的倍数，（但并不能断定k1m+k2n可以取任意正整数）
②、
对于k1和k2来说：k1和k2必然互质。若不互质，则其中一个是另一个的倍数，
假定k1是k2的倍数，则由a=k1d和b=k2d得知a也是b的倍数，则gcd(a,b)=b，
此时将得到k2=1的结论(而1与任何正整数互质)。
因此gcd(k1,k2)=1。
③、
设集合M{m|m=ax+by:x,y∈Z}，
设d是集合M的最小正整数，设e为集合M中除d外的其他数，
则由除法算法有e=di+j(其中i∈Z，0≤j＜d)。
因为e∈M且d∈M，所以di∈M，j∈M；
因为d是M的最小正整数，且j∈M，0≤j＜d，所以j只能取0，
因此e=di，这说明集合M中的元素都是d的倍数，即d|e。
设a、b互质，ax1+by1=e，
则a(x1+1)+by1=e+a，即(e+a)∈M，由d|e得d|(e+a)，
故d|a。同理得d|b。
由于d|a并且d|b，且a和b互质，所以d的取值只能是1
所以集合M的最小正整数是1，且其他元素均是1的倍数，或者说M与Z等价
(传送门——https://blog.csdn.net/jiejnan/article/details/6210327)
(感觉①和②是不是多余了)
④、
由②③得知，①中的a、b线性组合am+bn是d的倍数，
存在整数r和s使得ar+bs=d，即gcd(a,b)=ar+bs
2、实现GCD算法的迭代版本。
#include<iostream>
using namespace std;
typedef unsigned uint;
uint GCD(uint a, uint b) {//迭代版本
return a == 0 ? b :(b==0?a: (a>b?GCD(a%b,b):GCD(b%a,a)));
}
uint BGCD(uint a,uint b) {//二进制GCD算法
if (a == 0)//防崩
(a = b), (b = 0);
if (a == 0)//放崩二度
return 0;
auto swap = [](uint& a, uint& b) {
a ^= b;
b ^= a;
a ^= b;
};
uint pwr = 0;//指数。如果两个数都有明显的公因子，那可以先拿出来，即gcd(a,b)=gcd(ka',kb')=k*gcd(a',b')
for (; !((a | b) & 1); ++pwr)
(a >>= 1), (b >>= 1);
while (!(a & 1))//在辗转相除中，如果一个数有a=ka'形式，那么可以用a'把a替代。或者说，gcd(a,b)=gcd(ka',b)=gcd(a',b)
a >>= 1;
while (b) {
while (!(b & 1))
b >>= 1;
if (b<a)
swap(a, b);
b -= a;
}
return a << pwr;
}
int main() {
cout << GCD(15, 50) << endl;//输出结果：5
cout << BGCD(15, 50) << endl;//输出结果：5
return 0;
}
3、实现EGCD算法。输入：a、b两个整数，输出：r、s、d三个整数，满足ar + bs =d。
#include<iostream>
using namespace std;
typedef unsigned uint;
#include<vector>
vector<int> EGCD(uint a, uint b) {//勉强看懂，要从头写的话比较吃力。
int r, s, R, S;
r = S = 1;
R = s = 0;
while (b) {
uint q = a / b;
uint tmp = a % b;
a = b;
b = tmp;
tmp = r - q * R;
r = R;
R = tmp;
tmp = s - q * S;
s = S;
S = tmp;
}
return vector<int>{ (int)a,r,s };
}
vector<int> BEGCD(uint a, uint b) {//看不懂。考试要真被要求从零写出来的话，，我直接pass掉[doge][doge]
int r, s, R, S, pwr;
r = S = 1;
R = s = pwr = 0;
for (; !((a | b) & 1); ++pwr)
(a >>= 1), (b >>= 1);
int A, B;
A = a;
B = b;
auto swap = [](int& a, int& b) {
a ^= b;
b ^= a;
a ^= b;
};
while (B) {
while (!(A | 1)) {
A >>= 1;
if (!((r | s) & 1))
(r >>= 1), (s >>= 1);
else
(r = (r + b) >> 1),(s=(s-a)>>1);
}
while (!(B | 1)) {
B >>= 1;
if (!((R | S) & 1))
(R >>= 1), (S >>= 1);
else
(R = (R + b) >> 1), (S = (S - a) >> 1);
}
if (B < A)
swap(A,B), swap(r,R), swap(s,S);
B -= A;
R -= r;
S -= s;
}
return vector<int>{A<<pwr,r,s};
}
int main() {
auto egcd = EGCD(15, 50);
cout << egcd[0] << ' ' << egcd[1] << ' ' << egcd[2] << endl;//输出结果：5 -3 1
auto begcd = BEGCD(15, 50);
cout << begcd[0] << ' ' << begcd[1] << ' ' << begcd[2] << endl;//输出结果：5 -3 1
return 0;
}
4、实现一种批处理版本的GCD算法，即，给定一个整数数组，输出其中所有整数的最大公因子。输入：一个整数数组a；输出：一个整数d，是a数组中所有整数的最大公因子。
#include<iostream>
using namespace std;
typedef unsigned uint;
#include<vector>
uint BAT_EGCD(vector<uint> nums) {
uint tmp = 0;
uint pwr = 0;
for (auto p = nums.begin(); p != nums.end(); ++p)
tmp |= *p;
if (tmp == 0)//防崩
return 0;
for(;(tmp & 1) == 0;tmp>>=1)
++pwr;
for (auto p = nums.begin(); p != nums.end(); ++p) {
*p >>= pwr;
if (*p != 0 && *p < tmp)//找出nums的最小正值
tmp = *p;
}
uint min = tmp;
for(uint cnt=0;cnt!=nums.size();){//cnt统计nums中的0值个数，作为循环退出条件
tmp = min;
cnt = 0;
for (auto p = nums.begin(); p != nums.end(); ++p) {
if (*p == 0) {
++cnt;
continue;
}
while ((*p & 1) == 0)
*p >>= 1;
if (*p < tmp)
tmp = *p;
if (*p >= min)
*p -= min;
}
min = tmp;
}
return min << pwr;
}
int main() {
cout << BAT_EGCD(vector<uint>{18,54,108,30})<<endl;//输出结果：6
return 0;
}
