首页 > 其他分享 >【学习笔记】简单数论-同余

【学习笔记】简单数论-同余

时间:2023-08-18 17:03:36浏览次数:42  
标签:数论 ll 笔记 times pmod 逆元 同余 bmod equiv

  • 同余
    • 若整数 \(a\) 和整数 \(b\) 除以正整数 \(m\) 的余数相等,则称 \(a,b\) 模 \(m\) 同余,记为 \(a \equiv b \pmod{p}\) 。
      • 性质
        • 自反性: \(a \equiv a \pmod{p}\)
        • 对称性:若 \(a \equiv b \pmod{p}\) ,则 \(b \equiv a \pmod{p}\) 。
        • 传递性:若 \(a \equiv b \pmod{p},b \equiv c \pmod{p}\) ,则 \(a \equiv c \pmod{p}\) ;若 \(a \equiv b \pmod{p},q|p\) ,则 \(a \equiv b \pmod{q}\) 。
        • 同加性:若 \(a \equiv b \pmod{p}\) ,则 \(a+c \equiv b+c \pmod{p}\) 。
        • 同乘性:若 \(a \equiv b \pmod{p}\) ,则 \(a \times c \equiv b \times c \pmod{p}\) 。
        • 一般情况下不满足同除性。
          • 特例:当 \(\gcd(c,p)=1,a \times c\equiv b \times c \pmod{p}\) 时,则 \(a \equiv b \pmod{p}\) 。
        • 同幂性:若 \(a \equiv b \pmod{p}\) ,则 \(a^n \equiv b^n\pmod{p}\) 。
        • 若 \(p,q\) 互质,\(a \bmod p=x,a \bmod q=x\) ,则 \(a \bmod(p \times q)=x\) 。
    • 同余类与剩余系
      • 对于 \(\forall a \in[0,p-1]\) ,集合 \(\{a+kp\}(k \in \mathbb{Z})\) 的所有数模 \(p\) 同余,余数都为 \(a\) 。该集合称为一个模 \(p\) 的同余类,简记为 \(\overline{a}\) 。
      • 模 \(p\) 的同余类一共有 \(p\) 个,分别为 \(\overline{0},\overline{1},\overline{2},...,\overline{p-1}\) 。它们构成 \(p\) 的完全剩余系。
      • \(1 \sim p\) 中与 \(p\) 互质的数代表的同余类共有 \(\varphi(p)\) 个,它们构成 \(p\) 的简化剩余系。
        • \(p\) 的简化剩余系中的数满足与 \(p\) 互质且模 \(p\) 互不相同。
        • 若 \(a,b(1\le a,b\le p)\) 与 \(p\) 互质,有 \(a,b,(a \times b) \bmod p\) 属于 \(p\) 的简化剩余系。
    • 费马小定理
      • 若 \(p\) 是质数,则对于任意整数 \(a\) ,有 \(a^p \equiv a \pmod{p}\) 。
        • 证明:
          • 当 \(a\) 是 \(p\) 的倍数时,显然结论成立。
          • 当 \(a\) 不是 \(p\) 的倍数时,不存在一组 \(x,y\) 满足 \(1 \le x,y<p,xa \equiv ya \pmod{p}\) 。因此 \(1 \sim p-1\) 所有数,乘以 \(a\) 之后对 \(p\) 取模,仍可得 \(1\) ~ \(p-1\) 所有数。则 \(\prod\limits_{i=1}^{p-1} i \equiv \prod\limits_{i=1}^{p-1} ai \pmod{p}\) ,易知其中 \(\prod\limits_{i=1}^{p-1} i\) 与 \(p\) 互质,则 \(\prod\limits_{i=1}^{p-1}a \equiv 1 \pmod{p}\) ,即 \(a^{p-1} \equiv 1 \pmod{p}\) 。等式两边同乘 \(a\) ,得到 \(a^p \equiv a \pmod{p}\) 。
        • 变形
          • 若 \(\gcd(a,p)=1\) ,即 \(a\) 不是 \(p\) 的倍数,有 \(a^{p-1} \equiv 1 \pmod{p}\) 。
          • 若 \(\gcd(a,p) \ne 1\) ,即 \(a\) 是 \(p\) 的倍数,有 \(a^{p-1} \equiv 0 \pmod{p}\) 。
    • 欧拉定理
      • 若 \(\gcd(a,p)=1\) ,则 \(a^{\varphi(p)} \equiv 1 \pmod{p}\) 。
      • 证明:
        • 当 \(p\) 为质数时,有 \(a^{\varphi(p)}=a^{p-1}\) ,依据费马小定理,有 \(a^{p-1} \equiv 1 \pmod{p}\) 。
        • 当 \(p\) 不为质数时,设 \(S=\{ p_1,p_2,...,p_{\varphi(p)}\}\)为 \(p\) 的简化剩余系,对于任意一对 \(i,j(i \ne j)\) ,有 \((a \times p_i) \bmod p \ne (a \times p_j) \bmod p\) ,且 \(a \times p_i,a \times p_j\) 均与 \(p\) 互质。因此 \(S\) 中所有数,乘以 \(a\) 之后对 \(p\) 取模,仍可得 \(S\) 中所有数,则 \(\prod\limits_{i=1}^{\varphi(p)} i \equiv \prod\limits_{i=1}^{\varphi(p)} ai \pmod{p}\) ,易知其中 \(\prod\limits_{i=1}^{\varphi(p)} i\) 与 \(p\) 互质,则 \(\prod\limits_{i=1}^{\varphi(p)}a \equiv 1 \pmod{p}\) ,即 \(a^{\varphi(p)} \equiv 1 \pmod{p}\) 。
    • 扩展欧拉定理
      • \(a^b \equiv \begin{cases}a^{b \bmod \varphi(p)} ,\quad \qquad\gcd(a,p)=1\\a^{b} ,\quad \qquad \qquad \ \ \ \ \gcd(a,p) \ne 1,b<\varphi(p)\\a^{b \bmod \varphi(p)+\varphi(p)} ,\quad \gcd(a,p) \ne 1,b \ge \varphi(p)\end{cases} \pmod{p}\)
      • 证明极其复杂,请参考 link 或者 oiwiki 中的证明。
    • 乘法逆元
      • 如果存在一个线性同余方程 \(ax \equiv 1 \pmod{b}\) ,则 \(x\) 记作 \(a \bmod b\) 的乘法逆元(简称逆元),记作 \(a^{-1}\) 。
        • 若 \(b|a\) 时不存在 \(a\) 的逆元 \(a^{-1}\) 。
      • 特别地,有 \(1^{-1} \equiv 1 \pmod{b}\) 。
        • 证明:对于 \(\forall b \in \mathbf{Z}\) ,有 \(1 \times 1 \equiv 1 \pmod{b}\) ,故在 \(b\) 下 \(1\) 的逆元为 \(1\) 。
      • 性质
        • 若 \(n\) 为正整数,则 \(2 \bmod(2n+1)\)的乘法逆元为 \(n+1\) 。
          • 证明:已知 \(2x \equiv 1 \pmod{2n+1}\) ,设 \(2x=(2n+1)k+1\) ,又因为 \(2x\) 为偶数, \(k\) 的最小正整数解为 \(1\) ,代入得 \(x=n+1\) 。
      • 如何求逆元(边算边取模)
        • 扩展欧几里得
          • 限制条件: \(\gcd(a,b)=1\) 。
          • 设 \(ax=bk+1,y=-k\) ,原方程可改写为 \(ax+by=1\) ,用 \(exgcd\) 解得一组特解 \(x_0,y_0\) ,\(x\) 的最小正整数解为 \((x+b)\bmod b\) 。
          • 时间复杂度为 \(O(\log \max(a,b))\) 。
          • luogu P1082 [NOIP2012 提高组] 同余方程
          ll exgcd(ll a,ll b,ll &x,ll &y)
          {
          	if(b==0)
          	{
          		x=1;
          		y=0;
          		return a;
          	}
          	else
          	{
          		ll d=exgcd(b,a%b,y,x);
          		y-=a/b*x;
          		return d;
          	}
          }
          int main()
          {
          	ll a,b,x=0,y=0;
          	cin>>a>>b;
          	exgcd(a,b,x,y);
          	x=(x%b+b)%b;
          	cout<<x<<endl;
          }
          
          luoguP2613 【模板】有理数取余
          const ll p=19260817;
          ll exgcd(ll a,ll b,ll &x,ll &y)
          {
          	if(b==0)
          	{
          		x=1;
          		y=0;
          		return a;
          	}
          	else
          	{
          		ll d=exgcd(b,a%b,y,x);
          		y-=a/b*x;
          		return d;
          	}
          }
          int main()
          {
          	ll a,c,d,x=0,y=0;
          	c=read();
          	a=read();
          	d=exgcd(a,p,x,y);
          	if(c%d==0)
          	{
          		x=(x*c/d)%p;
          		x=(x%p+p)%p;
          		cout<<x<<endl;
          	}
          	else
          	{
          		cout<<"Angry!"<<endl;
          	}
          	return 0;
          }
          
      • 快速幂+费马小定理/欧拉定理
        • 限制条件: \(b\) 为质数。
        • 因为 \(b\) 为质数, \(ax \equiv 1 \pmod{b}\) ,依据费马小定理/欧拉定理,则 \(ax \equiv a^{b-1} \pmod{b}\) ,故 \(x \equiv a^{b-2} \pmod{b}\) 。用快速幂求出 \(a^{b-2} \bmod b\) ,即为所求。
        • 时间复杂度为 \(O(\log b)\) 。
        • luogu P1082 [NOIP2012 提高组] 同余方程
          ll qpow(ll a,ll b,ll p)
          {
          	ll ans=1;
          	a%=p;
          	while(b>0)
          	{
          		if(b&1)
          		{
          			ans=ans*a%p;
          		}
          		b>>=1;
          		a=a*a%p;
          	}
          	return ans%p;
          }
          int main()
          {
          	ll a,b;
          	cin>>a>>b;
          	cout<<qpow(a,b-2,b)<<endl;
          }
          
      • 线性求逆元(递推/递归)
        • 限制条件: \(b\) 为质数。
        • 设 \(k=\left\lfloor\dfrac{b}{i}\right\rfloor,r=b \bmod i\) ,此时有 \(b=k \times i+r,r<i\) ,进而得到 \(k \times i+r\equiv 0 \pmod{b}\) 。两边同时乘以 \(i^{-1} \times r^{-1}\) 得 \(k \times r^{-1}+i^{-1}\equiv 0 \pmod{b}\) ,移项得 \(i^{-1}\equiv -k \times r^{-1} \pmod{b}\) ,将 \(k=\left\lfloor\dfrac{b}{i}\right\rfloor,r=b \bmod i\) 代入得 \(i^{-1}\equiv -\left\lfloor\dfrac{b}{i}\right\rfloor \times (b \bmod i)^{-1} \pmod{b}\) ,考虑消除负数取模对答案的影响,故推出逆元:\(\\i^{-1} \equiv \begin{cases}1,&i=1\\(b-\left\lfloor\dfrac{b}{i}\right\rfloor) \times (b \bmod i)^{-1}&otherwise\end{cases} \pmod{b}\)
        • 递推求 \(N\) 个数的逆元, \(O(N)\) 预处理, \(O(1)\) 查询。
        • 递归+记忆化求 \(N\) 个数的逆元, \(O(N)\) 预处理, \(O(1)\) 查询。
        • 递归求 \(n\) 的逆元,时间复杂度为 \(O(n^{\dfrac{1}{3}})\) 。
        • luogu P3811 【模板】乘法逆元
          ll inv[3000001];
          int main()
          {
          	ll n,p,i;
          	cin>>n>>p;
          	inv[1]=1;
          	cout<<"1"<<endl;
          	for(i=2;i<=n;i++)
          	{
          		inv[i]=(p-p/i)*inv[p%i]%p;
          		cout<<inv[i]<<endl;
          	}
          	return 0;
          }
          
      • 线性求任意 \(n\) 个数的逆元(离线)
        • 限制条件: \(b\) 为质数。
        • 给定一个长度为 \(n\) 的序列 \(a(1 \le i \le n,1 \le a_i <p)\) ,分别求出 \(a_i^{-1}(1 \le n)\) 。令 \(mul[i]=\prod\limits_{k=1}^{i} a_i\) ,利用 \(exgcd\) 或快速幂计算 \(invc[n]=mul[n]^{-1}\) ,此时有 \(invc[i]=invc[i+1] \times a_{i+1}=mul[i]^{-1}\) ,那么 \(a_i^{-1}=mul[i-1] \times invc[i]\) 。
        • 时间复杂度为 \(O(n+\log b)\) 。
        • luogu P3811 【模板】乘法逆元
          ll mul[3000001],invc[3000001],inv[3000001],w[3000001];//防止重名,此处的w[]即为上文的a[]
          ll qpow(ll a,ll b,ll p)
          {
          	ll ans=1;
          	while(b>0)
          	{
          		if(b&1)
          		{
          			ans=ans*a%p;
          		}
          		b>>=1;
          		a=a*a%p;
          	}
          	return ans%p;
          }
          int main()
          {
          	ll n,p,i;
          	cin>>n>>p;
          	mul[0]=1;
          	for(i=1;i<=n;i++)
          	{
          		w[i]=i;
          		mul[i]=((mul[i-1]%p)*(w[i]%p))%p;
          	}
          	invc[n]=qpow(mul[n],p-2,p);
          	for(i=n-1;i>=1;i--)
          	{
          		invc[i]=((invc[i+1]%p)*((w[i+1])%p))%p;
          	}
          	for(i=1;i<=n;i++)
          	{
          		inv[i]=((invc[i]%p)*(mul[i-1]%p))%p;
          		cout<<inv[i]<<endl;
          	}
          	return 0;
          }
          

标签:数论,ll,笔记,times,pmod,逆元,同余,bmod,equiv
From: https://www.cnblogs.com/The-Shadow-Dragon/p/17641004.html

相关文章

  • 【学习笔记】简单数论-快速幂
    luoguP1226【模板】快速幂|取余运算#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definesortstable_sort#defineendl'\n'llqpow(lla,llb,llp){llans=1;while(b>0){if(b&1){......
  • 【学习笔记】简单数论-最大公约数
    一个整数\(N\)的约数上界为\(2\sqrt{N}\)。\(1\simN\)每个数的约数个数的总和大约为\(N\timeslogN\)。取模运算性质\((a+b)\bmodp=((a\bmodp)+(b\modp))\modp\),反之亦成立。\((a-b)\bmodp=((a\bmodp)-(b\modp))\modp\),反之亦成立。\((a\tim......
  • 【学习笔记】简单数论-质数
    质数的个数是无限的。试除法:若一个正整数\(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中有打印......