扩展欧几里得算法给定两个正整数m和n,我们计算它们的最大公因子d和两个整数a和b,使得am+bn=d.具体步骤描述如下：第一步：[初始化]置a’←b←1,a←b’←0,c←m,d←n.第二步：[除]设q和r分别是c

Question

扩展欧几里得算法
给定两个正整数m和n,我们计算它们的最大公因子d和两个整数a和b,使得am+bn=d.具体步骤描述如下：第一步：[初始化]置a’←b←1,a←b’←0,c←m,d←n.第二步：[除]设q和r分别是c除以d的商和余数.（我们有c=qd+r,且0≤r＜d.） 第三步：[余数为0?]如果r=0,算法终止；在此情况下,我们如愿地有am+bn=d.第四步：[循环]置c←d,d←r,t←a’,a’←a,a←t-qa,t←b’,b’←b,b←t-qb,返回第二步 怎么用c语言实现此算法

Answer 1

//欧几米德算法 //算法描述：给定两个正整数m和n,求他们的最大公因子. //1.[求余数]用m除以n并令r为所得余数 //2.[余数为0]若r=0,则算法结束,n即为所求答案 //3.[互换]置m←n,n←r,并返回步骤1. #include #include using namespace std; int main(int argc, char *argv[]) { int n,m; int r; cout > m >> n; cout