最大公因数与最小公倍数-gcd&lcm
2024-09-03 22:06:41
一、一些性质
\(gcd(a,b)=gcd(b,a)\)
\(gcd(-a,b)=gcd(a,b)\)
\(gcd(a,a)=|a|, gcd(a,0)=|a|\)
\(gcd(a,1)=1\)
\(gcd(a,b)=gcd(b, a mod b)\)
\(gcd(a,b)=gcd(b, a-b)\)
\(gcd(a,b)*lcm(a,b)=ab\)
\(a|t,b|t⇒lcm(a,b)\)
\(...\)
二、最大公约数-gcd
1.欧几里得辗转相除法
证明:
设\(a=qb+r\),\(d|a\)且\(d|b\),
\(∵a=qb+r,\)
\(∴r=a-qb,\)
\(∵d|a\)且\(d|b\)
\(∴d | a -qb\)
\(∴d | r\)
\(∴a,b\)的公因数都是\(b,r\)的公因数
\(∴gcd(a,b)=gcd(b,r)\)
代码实现:
int gcd(int a, int b){
return b == 0 ? a : gcd(b , a % b);
}
2.stein_gcd算法
代码实现:
int stein(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
if (a % 2 == 0 && b % 2 == 0) return stein(a >> 1, a >> 1) * 2; //当两数均为偶数时将其同时除以2至至少一数为奇数为止,记录除掉的所有公因数2的乘积k
else if (a % 2 == 0) return stein(a >> 1, b); //因为只有一个数含有2作为因数,所以除以2后gcd(a,b)不变
else if (b % 2 == 0) return stein(a, b >> 1); //同上
else return stein(abs(a - b), min(a, b)); //详情请查看'更相减损数'
}
三、最小公倍数-lcm
基于gcd(a,b)*lcm(a,b)=ab这条性质则可求出最小公倍数
好像stein算法不是很常用,但的确弥补了欧几里得算法的一些缺点
最新文章
- robot创建桌面图标(转载)
- [知识点]KMP算法
- [BTS] WCF-OracleDB
- 安卓开发错误:The type android.support.v4.app.TaskStackBuilder$SupportParentable cannot be resolved.
- 构建ASP.NET MVC4+EF5+EasyUI+Unity2.x注入的后台管理系统(2)-easyui构建前端页面框架[附源码]
- hadoop笔记之MapReduce原理
- jsp的原则执行
- 负载均衡软件LVS分析一(概念)
- 关于bedtools merge 功能中sort 命令的解释
- (详细)华为荣耀4X CHE-TL00H的usb调试模式在哪里打开的步骤
- Vue小项目二手书商城:(二)axios前后端数据交互
- LOJ 2550 「JSOI2018」机器人——找规律+DP
- JS实现分钟数和时间小时 格式的转换
- centos7安装redis设置开机启动
- 调用Bartender服务并打印bartender标签
- MyCAT 在 Cobar 的基础上,完成了彻底的 NIO 通讯,并且合并了两个线程池
- phantomjs试玩
- linux磁盘管理(RHEL)
- OpenLayers 3 之 地图视图(View)
- docker社区的geodata/gdal镜像dockerfile分析
热门文章
- [C]郝斌C语言课程大纲及笔记
- Sentry 开发者贡献指南 - SDK 开发(性能监控:Sentry SDK API 演进)
- HTML网页设计基础笔记 • 【第7章 盒子模型】
- CSS过渡、CSS动画
- 『无为则无心』Python函数 — 34、lambda表达式
- 初识python:hello world 仪式感
- unittest_expectedFailure预期用例失败(5)
- JMeter_jmeter-plugins插件的安装使用
- xml文件 加载properties文件的两种方法与注意事项
- vue组件中的.sync修饰符使用