更相减损法|辗转相减法
减法
2023-09-11 14:18:49 时间
时间复杂度
o(n)
题目代码
int gcd(int a,int b)
{
if(a==b)return a;
return a>b?gcd(a-b,b):gcd(b-a,a);
}
特殊情况
辗转相除法可以用来求若干个形如(p/q)^ri的数的最大公约数,其中:
——p/q不可以再表示为次幂的形式
——p、q、ri均为正整数
算法推导
求指数的最大公约数,即:
f(p^x , p^y) = p(x,y) = p(y,x-y) = f(p^y,p(x-y)) = f(p^y, p^x / p^y)
X要大于Y
特殊情况下的代码
LL gcd_sub(LL a,LL b)
{
if(b>a)swap(a,b);
if(b==1)return a;
return gcd_sub(b,a/b);
}
相关文章
- 高精度计算(三):大整数加法和减法(采用“万进制”)
- SICP 习题 (2.8) 解题总结:区间的减法
- 【华为OD机试真题 python】n进制减法 【2022 Q4 | 200分】
- 《惢客创业日记》2018.09.06(周四) 创业中的“减法”最痛苦。
- 【MATLAB教程案例38】语音信号的去噪方法matlab仿真学习——LMS自适应滤波,谱减法去噪滤波及维纳滤波等
- 应用谱减法进行语音去噪的算法研究
- LeetCode高频题29. 两数相除:不用加减乘除号,求加法,减法,乘法,除法
- Shell 减法
- CSDN日报190802:成就更好的自己,就是不停地做减法
- 《精通Unreal游戏引擎》一第5步 使用减法BSP继续创建地图
- [模板题]高精度减法
- 密度聚类总结 (DBSCAN、OPTICS 、DPC 、CFSFDP、 DENCLUE、 山峰、减法)
- Subtrative Clustering 减法聚类
- 计组 | 二进制减法
- 模2加法,模2减法,模2除法
- 补码如何代替减法运算以及补码的范围为何是-128到+127
- K倍动态减法游戏
- 2023华为OD机试 - N进制减法(JS)
- 华为OD机试 - N 进制减法(Python)| 真题+思路+考点+代码+岗位
- 华为OD机试 -N进制减法(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - N进制减法(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 【悦~】实现两个数减法
- 为什么委托的减法(- 或 -=)可能出现非预期的结果?(Delegate Subtraction Has Unpredictable Result)
- [CareerCup] 7.4 Implement Multiply Subtract and Divide 实现乘法减法和除法
- 【Python养成】:案例(设计三维向量类、实现向量的加法、减法以及向量与标量的乘法和除法运算、编写自定义类,模拟内置集、编写自定义类,模拟双端队列。)