辗转相除法和同余原理

2024-02-15 17:04
文章标签 原理 除法 辗转 同余

本文主要是介绍辗转相除法和同余原理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

辗转相除法和同余原理

  • 辗转相除法
  • 同余原理

辗转相除法

  辗转相除法就是用来求出两个数的最大公约数的方法,那么这个方法怎么用呢?举个例子:有两个数,a=12,b=8,要求这两个数的最大公约数,首先让a%b得到4,然后让a=b,b=a%b,即现在a=8,b=4;继续用a%b得到0,然后让a=b,b=a%b,现在a=4,b=0。当b等于0的时候,a的值就是原来两个数的最大公约数
  代码如下

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

证明辗转相除法就是证明以下关系
g c d ( a , b ) = g c d ( b , a m o d b ) a gcd(a,b)=gcd(b,a\bmod b )a gcd(a,b)=gcd(b,amodb)a
假设 a m o d b = r a\bmod b=r amodb=r
则需要证明 g c d ( a , b ) = g c d ( b , r ) gcd(a,b)=gcd(b,r ) gcd(a,b)=gcd(b,r)
因为 a m o d b = r a\bmod b=r amodb=r成立,所以下面连等式必定成立
a = b ∗ q + r \begin{align} a=b*q+r \end{align} a=bq+r
r = a − b ∗ q \begin{align} r=a-b*q \end{align} r=abq
其中q为自然整数
假设u是a和b的公共因子,则有:
a = s ∗ u b = t ∗ u \begin{split} a=s*u\\ b=t*u \end{split} a=sub=tu
将a和b带入到式子(1)当中得到
r = s ∗ u − t ∗ u ∗ q = ( s − t ∗ q ) ∗ u \begin{split} r &= s*u-t*u*q\\ &= (s-t*q)*u \end{split} r=sutuq=(stq)u
  这说明,u如果是a和b的公因子,那么u也是r的公因子,假设v是b和r的公因子,同理可得v也是a的公因子。
  综上,a和b的每个公因子,也是b和r的公因子,反之亦然。所以a和b的全体公因子集合 = b和r的全体公因子集合
g c d ( a , b ) = g c d ( b , a m o d b ) a gcd(a,b)=gcd(b,a\bmod b )a gcd(a,b)=gcd(b,amodb)a
证毕
  在求出a和b最大公约数r之后,最小公倍数就是
a ∗ b / r a*b/r ab/r
  转换成代码就是

int lcm(int a, int b)
{return a * b / gcd(a, b);
}

  在了解到以上前置知识后,来做一道题目
在这里插入图片描述
神奇的数字
  就用示例2为例,两个数分别是2和3,要求第4个神奇的数字,其实我们可以给出一个范围,使得第4个神奇的数字是在这个范围里面的,因为是第4个神奇的数字,那么这个数字最大不会超过2*4也就是8,范围就可以确定为【0,8】,因为即使没有3,求得可以被2整除的第4个数字最大也就是8了,由于又加了一个数字,那么在范围【0,8】内神奇数字的数目肯定是变多了的,那么第4个神奇数字必定是在【0,8】之间
  在确定了范围之后,我们可以定义一个函数f(x),该函数的返回值就是从0到x包含有多少个神奇数字。还是以2和3为例
在这里插入图片描述
  可以看到,在【0,8】范围内6既是2的倍数也是3的倍数,所以不管是对于2来说还是对于3来说,6都是神奇数字,即6被算作了两次神奇数字,那么我们只要进行去重,得到的神奇数字个数就是函数f(x)的返回值
  在确定了范围还有f(x)后,我们就可以使用二分法解决这道问题
代码如下:

long long gcd(int a, int b) //求最大公约数{return b == 0 ? a : gcd(b, a % b);}long long lcm(int a, int b) //求最小公倍数{return a * b / gcd(a, b);}//检查x右边有多少个数是可以被a或者b整除long long check(long long x, int a, int b) {return x / a + x / b - x / lcm(a, b);}int nthMagicalNumber(int n, int a, int b) {long long mod = 1e9 + 7;long long l = 0;long long r = (n % mod) * min(a, b);while (l < r) {long long m = (l + r) / 2;if (check(m, a, b) >= n)r = m;elsel = m + 1;}return l % (mod);}

同余原理

加法的同余原理
( a + b ) m o d c = a m o d c + b m o d c (a+b)\bmod c=a\bmod c+b\bmod c (a+b)modc=amodc+bmodc
乘法的同余原理
( a ∗ b ) m o d c = ( a m o d c ) ∗ ( b m o d c ) (a*b)\bmod c=(a\bmod c)*(b\bmod c) (ab)modc=(amodc)(bmodc)

  以加法的同余原理为例,当题目要求结果对c进行取模运算时,但是在得到结果的时候,也就是a+b运算过程中,加出来的结果已经超出了当前类型的最大值,就发生了溢出的现象,这个时候再对溢出后的结果进行取模已经没有意义了,所以就需要在运算之前就分别对两个数进行取模防止溢出

减法的同余原理
( a − b ) m o d c = ( ( a m o d c ) − ( b m o d c ) + c ) m o d c (a-b)\bmod c=((a \bmod c)-(b \bmod c)+c) \bmod c (ab)modc=((amodc)(bmodc)+c)modc
  在减法的同余原理中需要对
( a m o d c ) − ( b m o d c ) (amodc)−(bmodc) (amodc)(bmodc)加上c是为了防止两数相减得到一个负数的情况

这篇关于辗转相除法和同余原理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/711974

相关文章

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

Spring @Scheduled注解及工作原理

《Spring@Scheduled注解及工作原理》Spring的@Scheduled注解用于标记定时任务,无需额外库,需配置@EnableScheduling,设置fixedRate、fixedDe... 目录1.@Scheduled注解定义2.配置 @Scheduled2.1 开启定时任务支持2.2 创建

Spring Boot 实现 IP 限流的原理、实践与利弊解析

《SpringBoot实现IP限流的原理、实践与利弊解析》在SpringBoot中实现IP限流是一种简单而有效的方式来保障系统的稳定性和可用性,本文给大家介绍SpringBoot实现IP限... 目录一、引言二、IP 限流原理2.1 令牌桶算法2.2 漏桶算法三、使用场景3.1 防止恶意攻击3.2 控制资源

Python中使用uv创建环境及原理举例详解

《Python中使用uv创建环境及原理举例详解》uv是Astral团队开发的高性能Python工具,整合包管理、虚拟环境、Python版本控制等功能,:本文主要介绍Python中使用uv创建环境及... 目录一、uv工具简介核心特点:二、安装uv1. 通过pip安装2. 通过脚本安装验证安装:配置镜像源(可

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意

Nacos注册中心和配置中心的底层原理全面解读

《Nacos注册中心和配置中心的底层原理全面解读》:本文主要介绍Nacos注册中心和配置中心的底层原理的全面解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录临时实例和永久实例为什么 Nacos 要将服务实例分为临时实例和永久实例?1.x 版本和2.x版本的区别

apache的commons-pool2原理与使用实践记录

《apache的commons-pool2原理与使用实践记录》ApacheCommonsPool2是一个高效的对象池化框架,通过复用昂贵资源(如数据库连接、线程、网络连接)优化系统性能,这篇文章主... 目录一、核心原理与组件二、使用步骤详解(以数据库连接池为例)三、高级配置与优化四、典型应用场景五、注意事