本文共 556 字，大约阅读时间需要 1 分钟。

欧几里得算法（原始形式减法）证明

先看算法过程:

1、r=m-n (其中m>n)

2、循环直到 r=0

2.1 m=n

2.2 n=r

2.3 r=m-n

3、输出 n 我们按这个过程走一遍: m n n m-n m-n 2n-m 2n-m 2m-3n 2m-3n 5n-3m … am+bn km+tn km+tn (a-k)m+(b-t)n 按照算法，当(a-k)m+(b-t)n=0时，这时最大公约数为km+tn； (a-k)m+(b-t)n=0得:m/n=-(b-t)/(a-k);那么km+tn=[(at-kb)/(a-k)]*n; 他应满足[(at-kb)/(a-k)]*n=[1/|a-k|]*n;得|at-kb|=1；我们观察上面的 的过程，验算发现这个等式恒成立；故得证。 共同学习！

求最大公约数两种方式：

#include 
   
    using namespace std;int  gcd(int,int);int gcd_2(int ,int);int main(){    cout<
    
     <
     
      =1;i--)    {        if(m%i==0&&n%i==0)            break;    }    return i;}
     
    
   

转载地址：http://ailzi.baihongyu.com/