提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

欧几里得算法及其证明

算法 及其 证明 欧几里得
2023-06-13 09:11:41 时间

定义

证明

代码实现

复杂度O(log(a+b)) 

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

迭代更新

int gcd(int a,int b){
    while(b){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}

Q.E.D.

相关文章