首页 > 其他分享 >【学习笔记】简单数论-最大公约数

【学习笔记】简单数论-最大公约数

时间:2023-08-18 16:57:46浏览次数:40  
标签:right gcd 数论 dfrac bmod 笔记 times int 最大公约数

  • 一个整数 \(N\) 的约数上界为 \(2\sqrt{N}\) 。
    • \(1 \sim N\) 每个数的约数个数的总和大约为 \(N \times logN\) 。
    • 取模运算性质
      • \((a+b) \bmod p=((a \bmod p)+(b \mod p)) \mod p\) ,反之亦成立。
      • \((a-b) \bmod p=((a \bmod p)-(b \mod p)) \mod p\) ,反之亦成立。
      • \((a \times b) \bmod p=((a \bmod p) \times (b \mod p)) \mod p\) ,反之亦成立。
      • 引流两篇讲解负数取模的文章 link1 link2
    • 若 \(\forall a,b \in \mathbb{N}\) ,则 \(\gcd (a,b) \times \operatorname{lcm} (a,b)=a \times b\) 。
    • \(\gcd(a,b)\) 用符号记作 \((a,b)\) ,\(\operatorname{lcm}(a,b)\) 用符号记作 \([a,b]\) 。
    • 特别地,有 \(\gcd(a,0)=a\) 。
    • 九章算术·更相减损法
      • 若 \(\forall a,b \in \mathbb{N},a \le b\) ,则 \(\gcd (a,b)= \gcd (a,b-a)= \gcd (b,b-a)\) 。
        • 证明:设 \(d= \gcd(a,b),k_1= \frac{a}{d},k_2= \frac{b}{d}\) ,移项得 \(a=k_1 d,b=k_2 d\) ,又因为 \(d|(b-a),b-a=(k_2-k_1)d\) ,故 \(\gcd(a,b-a)= \gcd(k_1 d,(k_2-k_1)d)=d\) ,\(b\) 与 \(b-a\) 同理。
      • 若 \(\forall a,b \in \mathbb{N}\) ,则 \(\gcd(2a,2b)= 2\gcd(a,b)\) 。
      • 优化:luogu P2152 [SDOI2009] SuperGCD
        • 考虑对更相减损法进行优化:
          • 当 \(a,b\) 均为偶数时,有 \(\gcd(a,b)=2 \times \gcd(\dfrac{a}{2},\dfrac{b}{2})\) 。
          • 当 \(a\) 为偶数, \(b\) 为奇数时,有 \(\gcd(a,b)= \gcd(\dfrac{a}{2},b)\) 。
          • 当 \(b\) 为偶数, \(a\) 为奇数时,有 \(\gcd(a,b)= \gcd(a,\dfrac{b}{2})\) 。
        • 不压位高精TLE 压位高精AC
    • 欧几里得算法
      • 若 \(\forall a,b \in \mathbb{N}\) ,则 \(\gcd(a,b)= \gcd(b,a \bmod b)\) 。
        • 证明
          • 若 \(a<b\) ,则 \(\gcd(b,a \bmod b)=\gcd(b,a)=\gcd(a,b)\) 。
          • 若 \(a \ge b\) ,设 \(d= \gcd(a,b),a=q \times b+r(0 \le r <b)\) ,则 \(r=a \bmod b=a-q \times b\) ,又因为 \(d|a,d|b,d|(q \times b)\) ,则 \(d|(a-q \times b)\) ,即 \(d|r\) ,故 \(\gcd(a,b)=\gcd(b,r)=\gcd(b,a \bmod b)\) 。
      • 时间复杂度为 \(O(\log \max(a,b))\) 。
      • 代码实现
        int gcd(int a, int b)
        {
        	return b?gcd(b,a%b):a;
        }
        
    • 扩展欧几里得算法
      • 裴蜀定理(贝祖定理, \(Bézout\) 定理)
        • 对于任意整数 \(a,b\) ,存在一对整数 \(x,y\) ,满足 \(ax+by= \gcd(a,b)\) 。
          • 证明:
            • 当 \(b=0\) 时,有一对整数 \(x=1,y=0\) 满足 \(a \times 1+0 \times 0= \gcd(a,0)\) 。
            • 若 \(b>0\) ,则 \(\gcd(a,b)= \gcd(b,a \bmod b)\) 。假设存在一对整数 \(x,y\) ,满足 \(b \times x+(a \bmod b) \times y= \gcd(b,a \bmod b)\) ,又因为 \(b \times x+(a \bmod b) \times y=b \times x+(a-b \times \left\lfloor\dfrac{a}{b}\right\rfloor) \times y=a \times y+b \times (x-\left\lfloor\dfrac{a}{b}\right\rfloor \times y)\) ,所以令 \(x'=y,y'=x-\left\lfloor\dfrac{a}{b}\right\rfloor \times y\) ,此时有 \(ax'+by'= \gcd(a,b)\) 。
          • 例题:luogu P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目
          • 推广
            • 对于任意整数 \(a_1,a_2,a_3,...a_n\) ,存在与之相对应的整数 \(x_1,x_2,x_3,...,x_n\) ,满足 \(a_1 x_1+a_2 x_2+a_3 x_3+...= \gcd(a_1,a_2,a_3,...,a_n)\) 。
            • 例题:luogu P4549 【模板】裴蜀定理
      • 代码实现
        int exgcd(int a,int b,int &x,int &y)
        {
        	if(b==0)
        	{
        		x=1;
        		y=0;
        		return a;
        	}
        	else
        	{
        		int d=exgcd(b,a%b,y,x);
        		y-=a/b*x;
        		return d;
        	}
        }
        
        • 上述程序求出方程 \(ax+by= \gcd(a,b)\) 的一组特解 \(x_0,y_0\) ,并返回 \(a,b\) 的最大公因数 \(d\) 。
      • 对于更为一般的方程 \(ax+by=c\) ,它有整数解当且仅当 \(d|c\) 。
        • 令 \(\gcd(a,b)=d,p=\dfrac{b}{d},q=\dfrac{a}{d}\) 。
        • 特解:先求出 \(ax+by=d\) 的一组特解 \(x_0,y_0\) ,然后将 \(x_0,y_0\) 各乘上 \(\dfrac{c}{d}\) ,此时就得到了 \(ax+by=c\) 的一组特解 \(x'=\dfrac{c}{d} \times x_0,y'=\dfrac{c}{d} \times y_0\) 。
          • \(x\) 的最小正整数解为 \(x_{min}=x'+\left\lceil\dfrac{1-x}{p}\right\rceil \times p\) ,此时 \(y''=y'-\left\lceil\dfrac{1-x}{p}\right\rceil \times q\) 。
            • 若 \(y''>0\) ,即存在正整数解时,正整数解的数量为 \(\left\lfloor\dfrac{y''-1}{q}\right\rfloor +1\) ,\(x\) 的最大正整数解为 \(x_{max}=x'+\left\lfloor\dfrac{y''-1}{q}\right\rfloor \times p\) ,\(y\) 的最小正整数解为 \(y_{min}=((y''-1) \bmod q)+1\) ,\(y\) 的最大正整数解为 \(y_{max}=y'\) 。
            • 若 \(y'' \le 0\) ,即不存在正整数解时,所有整数解中 \(x\) 的最小正整数值为 \(x_{min}\) , \(y\) 的最小正整数值为 \(y_{min}=y'+\left\lceil\dfrac{1-y}{q}\right\rceil \times q\) 。
          • 例题:luogu P5656 【模板】二元一次不定方程 (exgcd)
        • 通解: \(x'=\dfrac{c}{d} \times x_0+pk,y'=\dfrac{c}{d} \times y_0-qk(k \in \mathbb{Z})\) 。其中 \(x_0,y_0,d\) 的定义同上, \(k\) 取遍整数集合。

标签:right,gcd,数论,dfrac,bmod,笔记,times,int,最大公约数
From: https://www.cnblogs.com/The-Shadow-Dragon/p/17640986.html

相关文章

  • 【学习笔记】简单数论-质数
    质数的个数是无限的。试除法:若一个正整数\(N\)为合数,则存在一个能整除\(N\)的数\(T\),其中\(2\leT\le\sqrt{N}\)。时间复杂度为\(O(\sqrt{N})\)。代码实现boolisprime(intn){ if(n<2) returnfalse; for(inti=2;i<=sqrt(n);i++) if(n......
  • 燧光Rhino-X+Unity开发笔记
    一.前言  该文档的目的是记录开发过程中使用的燧光RhinoX眼镜和Unity引擎和所遇到的问题及解决方式。二.相关文档1.PhinoX-Unity开发文档2.官网设备介绍三.开发环境1.Unity2020.3.472.Rhino-For-Unity-2020Plugin四.问题列表1.RhinoX设备基本参数如下:  操作系统为......
  • 笔记整理--C语言--Stack的三种含义 - 博客 - 伯乐在线——转载
    【转载】:原文http://www.ruanyifeng.com/blog/2013/11/stack.htmlStack的三种含义-博客-伯乐在线-转载Stack的三种含义学习编程的时候,经常会看到stack这个词,它的中文名字叫做”栈”。理解这个概念,对于理解程序的运行至关重要。容易混淆的是,这个词其实有三种含义,适用于......
  • JavaSE学习笔记day04
    IO流概念:OS的文件系统:(1)文件:文本文件、视频文件、音频文件、图像文件、可执行文件等等,这些文件都是由一个个字节组成的。(2)目录(文件夹):对文件进行归纳划分,将同类型的文件方法在同一个文件夹中,方便我们管理和使用。(3)资源访问路径:1)相对路径:相对于某一个文件夹......
  • 8.18集训笔记
    上午递归,文件B2064斐波那契数列P1255数楼梯点击查看代码#include<bits/stdc++.h>usingnamespacestd;//#defineTlonglongtypedeflonglongLL;//取别名,以后使用LL就是longlongconstintN=5e3+10;LLfib[N];LLf(intn){//递归if(n<=2)return......
  • 10.4K Star!程序员为程序员针对性优化的开源免费笔记
    平时我一直用Notion来记录内容为主,但也一直关注着其他开源产品。上周正好看到一款非常受欢迎的开源免费笔记,今天就推荐给大家:VNote。VNote一个由程序员为程序员打造的开源笔记应用,基于Qt开发,专注于使用Markdown来写作的群体。它提供完美的编辑体验和强大的笔记管理功能,使得使......
  • 笔记整理--C语言--失落的C语言结构体封装艺术 - 博客 - 伯乐在线——转载
    失落的C语言结构体封装艺术-博客-伯乐在线转载1.谁该阅读这篇文章本文是关于削减C语言程序内存占用空间的一项技术——为了减小内存大小而手工重新封装C结构体声明。你需要基本的C语言的基本知识来读懂本文。如果你要为内存有限制的嵌入式系统、或者操作系统内核写代码,那......
  • SpringSecurity实战笔记之Security
    =================================SpringSecurity========================================一、默认配置1、默认会对所有请求都需要进行认证与授权;2、默认使用httpBasic方式进行登录3、默认的用户名为user,密码在启动应用时在console中有打印......
  • 笔记整理--C语言--数组指针和指针数组的区别 - hongcha_717 - 博客园——转载
    【转载】:原文http://www.cnblogs.com/hongcha717/archive/2010/10/24/1859780.html数组指针和指针数组的区别数组指针(也称行指针)定义int(*p)[n];()优先级高,首先说明p是一个指针,指向一个整型的一维数组,这个一维数组的长度是n,也可以说是p的步长。也就是说执行p+1时,p要跨过n个......
  • SpringSecurity实战笔记之RESTful
    =================================RESTful========================================一、JsonPath1、github:https://github.com/json-path/JsonPath二、@JsonView使用步骤(用于解决同一个对象在不同的接口返回的字段不同的场景)1、使用接口来声明多个视图2、在值对象的get方法上指......