首页 > 其他分享 >数论基础A

数论基础A

时间:2024-12-29 17:41:09浏览次数:6  
标签:gcd 数论 基础 mid cdot beta alpha lcm

数论基础A


欧几里得算法(辗转相除法)求最大公约数GCD

有两个整数 \(a,b(a>b)\) ,记它们的最大公约数为 \(gcd(a,b)\),对于任意的 \(a,b\ne 0\) 满足等式 :

\[gcd(a,b)=gcd(b,a\% b) \]

  • 充分性证明:

    设 \(d\) 为 \(a,b\) 的最大公约数,那么有 \(d\mid a\) 和 \(d\mid b\) 成立,组合出 \(d\mid (a-kb),\ (k\in N)\) 也成立,其中 \(a-kb=a\%b\)

  • 必要性证明:

    设 \(d\) 为 \(a,a\% b\) 的最大公约数,那么有 \(d\mid a\) 和 \(d\mid (a-kb),\ (k\in N)\) 成立,同样可以组合出 \(d\mid b\) 成立

程序设计中可以递归求解,递归出口为 \(a,b=0\) ,其中不为 \(0\) 的项即为最大公约数(\(a>b\))

int gcd(int a, int b){
	if (b == 0) return a;
	return gcd(b, a % b);
}
  • 复杂度分析:

    对 \(a\) 取 \(b\) 的模时,至少可以将 \(a\) 缩小到 \(a/2\) ,即 \(a\% b \le a/2\) ,证明如下

    • \(b< a/2\) 时,\(a\% b<b< a/2\)
    • \(b>a/2\) 时,\(a\%b=a-b\le a/2\)
    • \(b=a/2\) 时,\(a\% b=0<a/2\) (特殊状况,\(b\) 为 \(a\) 因子)

最小公倍数LCM

有两个整数 \(a,b(a,b\ne 0)\) ,记它们的最小公倍数为 \(lcm(a,b)\),对于任意的 \(a,b\ne 0\) 满足等式 :

\[lcm(a,b)=\frac{a\times b}{gcd(a,b)} \]

计算LCM需要先计算出GCD,采用先除后乘防止溢出

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

算数基本定理(整数惟一分解定理)

对于任意的一个正整数 \(n\) ,有且仅有一种由质数的乘积所表达的方式

\[n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\cdot\cdot p_s^{\alpha_s} \quad \quad p_1<p_2<\cdot \cdot\cdot<p_s \]

  • \(n\) 至多含有一个大于 \(\sqrt{n}\) 的质因子

    根据上述的表达方式可以反推,若有两个大于 \(\sqrt{n}\) 的质因子,它们的乘积一定大于了 \(n\)

  • 证明LCM表达式

    设 :

    \[a=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\cdot\cdot p_s^{\alpha_s} \\ b=p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\cdot\cdot p_s^{\beta_s} \]

    那么 \(gcd(a,b)\) 与 \(lcm(a,b)\) 可表示为

    \[gcd(a,b)=p_1^{min(\alpha_1,\beta_1)}\cdot p_2^{min(\alpha_2,\beta_2)}\cdot\cdot\cdot p_s^{\min(\alpha_s,\beta_s)} \\ lcm(a,b)=p_1^{max(\alpha_1,\beta_1)}\cdot p_2^{max(\alpha_2,\beta_2)}\cdot\cdot\cdot p_s^{\max(\alpha_s,\beta_s)} \]

    因为满足以下的约束条件

    \[min(\alpha_i,\beta_i)+max(\alpha_i,\beta_i)=\alpha_i+\beta_i \]

    所以有

    \[gcd(a,b)\times lcm(a,b) =p_1^{\alpha_1+\beta_1}\cdot p_2^{\alpha_2+\beta_2}\cdot\cdot\cdot p_s^{\alpha_s+\beta_s} = a\times b \]

标签:gcd,数论,基础,mid,cdot,beta,alpha,lcm
From: https://www.cnblogs.com/dianman/p/18639293

相关文章

  • 【Java基础-28】访问修饰符对方法重写的影响:深入解析与最佳实践
    在Java中,方法重写(MethodOverriding)是实现多态性的核心机制之一。通过方法重写,子类可以提供与父类中同名方法的具体实现,从而定制或扩展父类的行为。然而,在方法重写的过程中,访问修饰符(AccessModifiers)的选择对方法的可见性和行为有着重要影响。本文将深入探讨访问修饰符对方......
  • 2024-2025-1 20241327 《计算机基础与程序设计》第十四周学习总结
    作业信息|2024-2025-1-计算机基础与程序设计)||--|-|2024-2025-1计算机基础与程序设计第十四周作业)||快速浏览一遍教材计算机科学概论(第七版),课本每章提出至少一个自己不懂的或最想解决的问题并在期末回答这些问题|作业正文|https://www.cnblogs.com/shr060414/p/18440575|......
  • 2024-2025-1 20241423 《计算机基础与程序设计》第十四周学习总结
    作业信息这个作业属于哪个课程<班级的链接>(如2024-2025-1-计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>(如2024-2025-1计算机基础与程序设计第十四周作业)这个作业的目标无作业正文...本博客链接教材学习内容总结文件操作相关基础通常会介......
  • 【OpenGL ES】GLSL基础语法
    1前言​本文将介绍GLSL中数据类型、数组、结构体、宏、运算符、向量运算、矩阵运算、函数、流程控制、精度限定符、变量限定符(in、out、inout)、函数参数限定符等内容,另外提供了一个include工具,方便多文件管理glsl代码,实现代码的精简、复用。​Unity中Shader介......
  • 2024-2025-1 20241425 《计算机基础与程序设计》第14周学习总结
    2024-2025-120241425《计算机基础与程序设计》第14周学习总结作业信息这个作业属于哪个课程<班级的链接>(https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP/这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK14这个作业的目标<写上......
  • 2024-2025-1 20241428 《计算机基础与程序设计》第十四周学习总结
    学期(如2024-2025-1)学号《计算机基础与程序设计》第14周学习总结作业信息这个作业属于哪个课程<班级的链接>(如2024-2025-1-计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>(如2024-2025-1计算机基础与程序设计第一周作业)这个作业的目标<写上具体方面>......
  • 2024-2025-1 20241314 《计算机基础与程序设计》第十四周学习总结
    2024-2025-120241314《计算机基础与程序设计》第十四周学习总结作业信息这个作业属于哪个课程<班级的链接>(如2024-2025-1-计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>2024-2025-1计算机基础与程序设计第十四周作业作业正文正文教材学习内容总......
  • C语言学习笔记(基础语法篇)
    C语言学习笔记(基础语法篇)序言首先事先说明一下,这是我从各处整理的,当初刚接触CS,甚至连标注意识都没有,再次感谢写这些文章的人.当然这里不是说全部都是别人写的了,也有一点我自己的思考.首先是几个注意点:结构化,模块化,分而治之多写注释,多调试指针也有不同类型......
  • 2024-12-05《关于pip总是下载到基础环境不下载到虚拟环境》
    关于pip总是下载到基础环境不下载到虚拟环境 今天使用pip安装包报错了,使用piplist查询了一下发现竟然默认安装在了基础环境里,我激活了conda的虚拟环境再运行pip依然是安装在了基础环境里,百度后发现解决方法为去除掉系统环境变量里的PYTHONHOME然后使用虚拟环境变量里的虚拟......
  • PYTHON语言学习笔记(基础语法篇)
    Python学习笔记序言主要是以小甲鱼的视频为主,https://space.bilibili.com/314076440一些特性多次调用方法是从左到右.而参数是函数则先执行参数.一行如果要多个赋值,用;隔开input().split()IO看我放在另一个地方的文档.<D:\Document\md\PYTHON\IO.md>数据类型变量没什......