首页 > 编程语言 >最大公约数 C/C++ leetcode , 辗转相除,更相减损

最大公约数 C/C++ leetcode , 辗转相除,更相减损

时间:2022-11-12 03:33:06浏览次数:46  
标签:return 更相 int 最大公约数 相除 else 减损 while

#include <iostream> using namespace std;
// 辗转相除法求最大公约数, 用大的模小的,然后用除数模余数,该接口在新版的C++17的numeric 包中也有 int gcd1(int a ,int b ){     if(a>b){         while(a%b != 0 ){             int c = a%b;             a = b;             b = c;         }         return b;     }          else{         while(b%a != 0){             int c = b%a;             b = a;             a = c;         }         return a;     } }
//更相减损术求最大公约数,  用大的减去小的,然后用较大的再减较小的,一直到两者一样。 int gcd2(int a,int b){     if(a>b){         while(a != b){             int c = a-b;             if(c > b) {a = c;}             else {a = b;b = c;}         }     }     else{         while(b != a){             int c = b-a;             if(c > a) {b = c;}             else {b=a;a = c;}         }     }     return a; }
int main() {     int a, b;     while (cin >> a >> b) { // 注意 while 处理多个 case         int c = gcd2(a,b);         cout<<a/c * b;     }
}

标签:return,更相,int,最大公约数,相除,else,减损,while
From: https://www.cnblogs.com/daniel123/p/16882614.html

相关文章

  • 欧几里得(辗转相除法)求两个数最大公约数
    #include<stdio.h>intEA(inta,intb)//欧几里得算法{intremainder;intmiddle;if(a<b)//a,b交换值{b=a+b;a......
  • 29. 两数相除
    29.两数相除题解:a/b=y等价于b>a-(b*y)>0,只要求出减了多少次b就好了。一个一个地减b,效率太低了,最坏情况下,a=2^31-1,b=1,超时;应该先预......
  • BZOJ 4031([HEOI2015]小Z的房间-矩阵树定理+辗转相除)
    矩阵树定理,注意gauss消元辗转相除的写法#include<bits/stdc++.h>usingnamespacestd;#define#define#define#define#define#define#define#define#define#define#define#d......
  • 辗转相除的时间复杂度
    \(\gcd(a,b)=\gcd(b,a\%b)\)这是辗转相除法,也叫欧几里得算法欧几里得算法的时间复杂度我们认为是\(O(logn)\)的。证法1设\(a>b\)分为两种情况:①\(a>2b\)发......
  • sql server两整数相除向上取整
    ---------【向上取整】---------------------------------------------------------------------------------------------------------SELECTCEILING('1.06')--2--两......
  • C语言:辗转相除法求最大公约数 函数
    #include<stdio.h>//求最大公约数:辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。//319377:319%377=319377%319=58319%58=2958%29=0......
  • C语言:辗转相除法求最大公约数
    #include<stdio.h>//求最大公约数:辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。//319377:319%377=319377%319=58319%58=2958%29=0......
  • C语言:九章算术:更相减损法求最大公约数 函数写法
    #include<stdio.h>//<<九章算术>>更相减损法:可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。//以等数约之。///第......
  • C语言:九章算术更相减损法求最大公约数
    #include<stdio.h>//<<九章算术>>更相减损法:可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。//以等数约之。///第......
  • 29. 两数相除
     难度中等966收藏分享切换为英文接收动态反馈给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和mod运算符。返回被除数 divi......