首页 > 其他分享 >辗转相除法求最大公因数

辗转相除法求最大公因数

时间:2023-05-23 20:13:43浏览次数:35  
标签:除法 return int 辗转 include 公因数

image

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int a, b;
//辗转相除法求最大公因数
int gcd (int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main()
{
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    
    return 0;
}

标签:除法,return,int,辗转,include,公因数
From: https://www.cnblogs.com/fghjktgbijn/p/17426237.html

相关文章

  • Scala中实现和Python一致的整数除法和整数求余
    \[\color{black}{\text{Inscala,it'sweirdtomimic`%``//`ofpython}}\]/*Python's%operatorreturnsaresultwiththesamesignasthedivisor,and//roundstowardsnegativeinfinity.InScala,%and/don'tbehavethesameway.......
  • 数据分析缺失值处理(Missing Values)——删除法、填充法、插值法
    缺失值指数据集中某些变量的值有缺少的情况,缺失值也被称为NA(notavailable)值。在pandas里使用浮点值NaN(NotaNumber)表示浮点数和非浮点数中的缺失值,用NaT表示时间序列中的缺失值,此外python内置的None值也会被当作是缺失值。需要注意的是,有些缺失值也会以其他形式出现,比如说用NULL......
  • 带余除法
    题目描述:给定被除数和除数,求整数商及余数。输入格式:一行,包含两个整数,依次为被除数和除数(除数非零),中间用一个空格隔开。输出格式:一行,包含两个整数,依次为整数商和余数,中间用一个空格隔开。样例输入:103样例输出:31 ......
  • A除以B(千位数除法)
    本题要求计算 A/B,其中 A 是不超过1000位的正整数,B 是1位正整数。你需要输出商数 Q 和余数 R,使得 A=B×Q+R 成立。输入格式:输入在一行中依次给出 A 和 B,中间以1空格分隔。输出格式:在一行中依次输出 Q 和 R,中间以1空格分隔。 #include<iostream>#incl......
  • codeforces 267A A. Subtractions(辗转相除)
    题目链接:codeforces267A题目大意:给出一个数对,(a,b)每次用较大的减较小的,直到出现0为止,问要进行多少次操作。题目分析:大的减小的操作,可以利用取模优化过程,也就是辗转相除,商是操作次数,余数是下一段与之前较小的数继续进行操作的数,水题不做赘述。AC代码:#include<iostream>#include......
  • java8 BigDecimal 除法保留三位小数 (舍去小数三位后的数,四舍五入)
    BigDecimala=newBigDecimal("9");BigDecimalb=newBigDecimal("15");//舍去小数三位后的数BigDecimalc=b.divide(a,3,RoundingMode.HALF_UP);System.out.println(c);//四舍五入BigDecimal......
  • 最大公因数和最小公倍数
    publicclassMain{publicstaticvoidmain(String[]args){inta=12,b=18;intgcd=gcd(a,b);intlcm=lcm(a,b);System.out.println("最大公因数:"+gcd);System.out.println("最小公倍数:"+lc......
  • 力扣题目整数除法
    在力扣上做题,这个题涉及到的整数溢出问题十分恼人,主要也是我不熟悉这些东西,做的很艰难,下面是题目:给定两个整数a和b,求它们的除法的商a/b,要求不得使用乘号'*'、除号'/'以及求余符号'%'。注意:整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345)=8以及......
  • 从0开始自制解释器——添加对乘除法的支持
    在上一篇中,我们实现了对减法的支持,并且介绍了语法图。针对简单的语法进行描述,用语法图描述当然是没问题的。但是针对一些复杂的语法进行描述,如果每个部分都通过语法图来描......
  • 数学知识模板之试除法
    试除法判定质数boolis_prime(intx){ if(x<2)returnfalse; for(inti=2;i<=x/i;i++) if(x%i==0)returnfalse; returntrue;}试除法分解质因......