当前位置：主页 > 查看内容

【数论】ACM数论知识总结

发布时间：2021-05-10 00:00| 有位朋友查看

简介：待更新…… 文章目录一.质数 1.定义 2.质数的判断 3.质数的筛选 4.质因子分解 5.互质二.同余 1.模运算 2.定义 3.同余的性质 4.欧拉定理 5.贝祖定理 6.扩展欧几里得 7.中国剩余定理 8.一般的线性同余方程组数论是数学的一个分支研究的是整数的性质。本篇文……

待更新……

文章目录

数论是数学的一个分支，研究的是整数的性质。本篇文章总结的是数论在ACM中的常见应用。

一.质数

1.定义

质数，又称素数，若一个正整数无法被除了1和它自身以外的其它数整除，则称其为质数，否则为合数。特殊地，1既不是合数也不是质数

2.质数的判断

给定一个数，判断是否为质数的方法：

试除法： 检查所有可能成为n的因子的数，若没有找到因子，则证明这个数是一个质数

一种朴素的做法就是从2遍历到N-1观察有无N的因子，若没有则说明N为质数，依据的想法是N的因子必然在1~N的范围内

改进： 其实我们只要找到一个N的因子（除了1和它本身）就可以证明N是个合数。

定理：如果N是一个合数，则必然存在一个N的因子T，满足 $2 \leq T \leq \sqrt N$

证明：反证法即可，假设合数N的所有因子都大于 $\sqrt N$ ，则任取一因子X，因为X为N的因子，所以N/X也是N的一个因子，而由于X大于 $\sqrt N$ ，所以N/X必然小于 $\sqrt N$ ，与假设相矛盾

根据这个定理，我们只需要从2遍历到√N即可，时间复杂度缩小为 $O （ \sqrt N ）$ ，若没找到因子则N为质数。

其它的想法：

素数筛进行预处理，用prime数组存放所有素数，然后从 $p r i m e [1]$ 遍历到 $p r i m e [i] ? p r i m e [i] \leq N$ ，因为N如果是合数，则必然存在小于等于√N的素数因子

证明：前文已经证明过必然存在小于等于√N的因子，如果这个因子是素数自不必说，如果是合数，那么合数可以被分解为素因子的乘积。

目的：可以进一步减少时间复杂度，需要遍历的数更少了（因为素数的分布相对稀疏，10万以内的素数只有9500多个）

当然这只是我个人的想法，没有仔细的验证与思考，并且大部分时候O（√N）的复杂度就已经很优秀了

3.质数的筛选

筛选：即从1~N中筛选出所有的质数

思路：一个数x的倍数——2x,3x,4x……必然不是素数

具体做法：从2开始扫描所有的数x，并将x的所有倍数标记为合数。如果扫描到一个数y，发现y没被标记过，说明y一定是素数，因为2~y-1没有y的因子，符合素数定义

因为每个合数必然有质因子，所以只让素数来进行标记的工作以减少重复标记，比如27让3来标记为合数即可。

这就是埃氏筛

缺点：有些数仍会被重复标记，比如12既是3的倍数又是2的倍数，具有多个质因子的数会被重复标记

改进：

线性筛/欧拉筛：

即找到一个数的唯一产生方式：让一个数的最小质因子对其进行标记，比如12，虽然有2，3两个质因子，但只让2来标记12。

时间复杂度接近 $O (N)$ ，所以称为线性筛

实现：

int Prime[100005];    //存放所有的质数
bool Isprime[100005]; //判断一个数是否为质数
int cnt=1;

void get_Prime(){
  for(int i=2;i<=100000;i++) Isprime[i]=1; //先默认所有数为质数
  for(int i=2;i<=100000;i++){
    if(Isprime[i]) Prime[cnt++]=i;
    for(int j=1;j<cnt&&Prime[j]*i<=100000;j++){ 
        Isprime[Prime[j]*i]=0; //将其标记为合数
        if(i%Prime[j]==0)
            break;
    }
  }
}

对于if(i%Prime[j]==0) break; 的解释：

线性筛的思想是只让最小质因子对合数进行标记，也就是：Isprime[Prime[j]*i]=0; 这句话，这里Prime[j]即最小质因子。

如果i%Prime[j]==0 ，不妨将i表示为k*Prime[j]，如果令j++继续筛下去的话，下一个要筛的数是Prime[j+1]*i，显然这个数的最小质因子应该是Prime[j]而不是Prime[j+1]，违背了线性筛的思想，所以需要break

4.质因子分解

算术基本定理：

任何一个大于1的正整数都可以被分解为质因子的幂次的积

即 $N=P_1^{a_1}\cdot P_2^{a_2}\cdot P_3^{a_3}\cdot\cdot\cdot P_m^{a_m}$

这个定理看似非常简单，但是在很多地方都会应用到，要有将一个数分解为质因子幂次乘积的思想

分解质因子：

int factor[100];
int cnt=0;

void divide(int N){
    cnt=0;
    for(int i=2;i*i<=N;i++){
       if(N%i==0){
         factor[cnt++]=i;
         while(N%i==0)
            N/=i;
       }
    }
    if(N>1)  factor[cnt++]=N; //质数在根号N内没有因子，故可能没除完
}

如果还想知道每个质因子的幂次再用一个数组存就行

5.互质

最大公约数：great common divisor，简称gcd。两个数的最大公约数即两个数共有的约数（因子）中值最大的数。

互质定义：若gcd(a,b)=1，则称a与b互质。（即不含共同因子）

常见的求gcd的方法为欧几里得算法，时间复杂度为 $O (l o g (N))$ 的级别

关于欧几里得算法求gcd的证明：欧几里得算法证明

欧拉函数：

在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。例如φ(8)=4，因为1,3,5,7均和8互质。

具体信息可见：欧拉函数计算及打表

二.同余

1.模运算

对于任意的两个整数a、b(b>0)，必然存在等式：

$a = k b + r$

其中k为a除以b的商，r为a除以b的余数。在C语言中，可以利用a/b得到k，利用a%b得到r。前者称为整除，后者即模运算。

模运算的实质其实就是a-kb

性质：

① $(a+b)\%p=(a\%p+b\%p)\%p$

② $(a-b)\%p=(a\%p-b\%p+p)\%p$ （加p防止结果变为负数）

③ $(a*b)\%p=(a\%p)*(b\%p)\%p$

④除法不满足分配律，需要用到乘法逆元将除法转化为乘法：

乘法逆元：

若 $b\cdot b^{-1} ≡ 1（mod\ p)$

则称 $b^{-1}$ 为b在模p下的乘法逆元，可以理解为模p意义下的倒数

则 $a/b)\%p=a*b^{-1}\%p$ 将除法转化为了乘法

乘法逆元存在的前提是 $g c d (b, p) = 1$

在ACM中用到的模数p一般都是质数，所以只要b不为0或p的倍数即可。

若p不是质数，则要求b、p互质

逆元求法：

一个数在模p意义下的乘法逆元有很多种求法，这里写一下我常用的一种求逆元的方法：

费马小定理：

p为质数且gcd(b,p)=1，则 $b^{p-1}≡ 1（mod\ p)$

也就是说 $b^{p-1}\%p=1$

可以验证一下：

当p=3时， $2^2,4^2,5^2,7^2$ 模p都等于1

而 $b^{p-1}=b^{p-2}\cdot b$

所以b的一个乘法逆元为 $b^{p-2}$ ，用快速幂即可较快求得

long long inv(long long x){
   return quickpow(x,mod-2)%mod;
}

⑤快速乘法

C自带的乘法运算很优秀，但是在计算 $a\cdot b \%p$ 时，如果p很大，即使使用分配律还是可能会超过数据类型上限，所以可以使用快速乘法来避免这个问题，不会快速乘的可以看这篇↓：

快速幂+快速乘法

2.定义

若整数a和整数b除以正整数m的余数相等(即 $a\% m=b\%m$ )，则称a，b模m同余，记为 $a≡b(mod\ m)$

下面的只要大概知道个概念就好

同余类：

亦称剩余类，为数论的基本概念之一。设模为m，则根据余数可将所有的整数分为m类：

把所有与整数a模m同余的整数构成的集合叫做模m的一个剩余类，记作[a]。（也见过a上面加一杠的写法）并把a叫作剩余类[a]的一个代表元。

例：在模5意义下，3、8、13都属于同余类[3]

简化剩余系：

同余类的集合构成了m的完全剩余系

简化剩余系指m的完全剩余系中与m互质的数的集合

简化剩余系关于模m乘法封闭，设a、b为简化剩余系中任意两个数，则a×b必然也属于简化剩余系

3.同余的性质

介绍在下面要用到的一些同余的性质

①若 $a≡b(mod\ n)$ 则 $a*c≡b*c(mod\ n)$

②若 $\ n)$ 则 $a^q≡b^q(mod\ n)$

③若 $a≡b(mod\ n), c≡d(mod\ n)$ ，则 $a*c≡b*d(mod\ n)$

由乘法对于模运算的分配律可以证明↑

①②可由③推得

其他性质可参见百度百科

4.欧拉定理

若正整数a，n互质，则 $a^{φ(n)}≡1(mod \ n)$

~~证明不会~~

费马小定理其实就是欧拉定理在n为素数时的特殊情况

推论：

若a，n互质，b为任意正整数，则 $a^b≡a^{b\ mod \ φ(n)}(mod \ n)$

——————————————————————————

证明：

令 $b = q ? φ (n) + r$ ，则：

$a^b≡a^{q*φ(n)+r}≡(a^{φ(n)})^{q}*a^r≡1^q*a^r≡a^r≡a^{b\ mod \ φ(n)}(mod \ n)$

——————————————————————————

应用：

前面已经说明了，加减乘除的模运算处理方式，这个推论可以以应用于幂次运算的模运算处理方式

$a^b\%p=(a\%p)^{b\%φ(p)}$

当然，一般来说快速幂 $l o g (N)$ 级别的复杂度已经足够优秀

引理：

a,n互质，满足 $a^x≡1 (mod \ n)$ 的最小正整数x一定是 $φ (n)$ 的约数

反证法：

假设满足条件的最小正整数 $x_0$ 不是 $φ (n)$ 的约数

首先 $a^{φ(n)}≡1(mod \ n)$ 是一定成立的，所以 $x_0<φ(n)$

令 $φ(n)=q*x_0+r\ (0<r<x)$

因为 $a^{x_0}≡1(mod\ n)$

所以 $a^{q*x_0}≡(a^{x_0})^q≡1(mod \ n)$

因为 $a^{φ(n)}≡a^{q*x_0+r}≡a^{a*x_0}*a^r≡1(mod \ n)$

所以 $a^r≡1(mod\ n)$

因为r< $x_0$ 所以假设不成立

5.贝祖定理

对任意整数a、b，存在一对x、y满足 $a x + b y = g c d (a, b)$

证明：

欧几里得算法求gcd(a,b)时：

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

递归函数的终点是a%b==0，此时gcd(a,b)==b， $a x + b y = g c d (a, b)$ 明显是有解的，易得x=0，y=1为一组特解

运用数学归纳法，只要证明：

$\% b)*y=gcd(b, a\%b)$ 有解，则 $a x + b y = g c d (a, b)$ 必有解

那么贝祖定理就成立了

$a\%b=a-b*[a/b]\ ([a/b]表示整除）$

$\% b)*y$

$= = b ? x + (a ? b ? [a / b]) ? y$

$= = a ? y + b ? (x ? [a / b] y)$

$==gcd(b.a\%b)$

$= = g c d (a, b)$

所以令 $x^{'}=y,y^{'}=x-[a/b]y$ ，则 $ax^{'}+by^{'}=gcd(a,b)$

综上，贝祖定理成立

6.扩展欧几里得

由上述的思路，可以写出扩展欧几里得的算法

代码如下：

long long  exgcd(long long  a,long long  b,long long  &x,long long &y){
   if(a%b==0) {x=0;y=1;return b;}
   long long  d=exgcd(b,a%b,x,y);
   long long temp=x; x=y;y=temp-(a/b)*y;
   return d;
}

应用：

①解不定方程ax+by=gcd(a,b)

函数返回的两个值x，y就是不定方程的一组特解

对于更一般化的方程ax+by=c，它有解当且仅当 $c\%gcd(a,b)==0$

我们可以先解出ax+by=gcd(a,b)的一组特解，然后令其同时乘上 $\frac{c}{gcd(a,b)}$ 即得方程ax+by=c的特解 $x_0,y_0$

方程ax+by=c的通解可以表示为

$x=x_0+k\cdot \frac{b}{gcd(a,b)}$

$y=y_0-k\cdot \frac{a}{gcd(a,b)}$

求x的最小正整数解：

$\frac{b}{gcd(a,b)}$

则最小正整数解为 $x_0\%temp+temp)\%temp$

更正：此处并不是最小正整数解，而是最小非负整数解，在答案可能为0的时候需要特判

②解线性同余方程

扩欧可以解决这种形式的同余方程：ax≡c(mod b) (1<c<b)

该方程显而易见可以转化为不定方程ax+by=c

③求逆元：

逆元的定义 $a*a^{-1}≡1(mod \ p)$

将逆元 $a^{-1}$ 表示为x

则可以转化为不定方程 $a ? x + p ? y = 1$

该方法相比于小费马定理略显麻烦，但是应用范围更广，只要求a、p互质即可，而小费马定理要求p为质数

7.中国剩余定理

线性同余方程：

形如a*x≡b (mod m)的方程，因为未知数x的指数为1，所以称为一次同余方程或线性同余方程

该方程要么无解，要么有无数个解

可以使用扩展欧几里得算法求解这类方程

一元线性同余方程组：

中国剩余定理（孙子定理）可以用于解决如下形式的线性同余方程组：

在这里插入图片描述
其中 $m_1,m_2\cdot\cdot\cdot,m_n$ 是两两互质的整数

令 $m=∏_{i=1}^nmi \ ,\ \ M_i=m/mi$

令 $t_i$ 为线性同余方程 $t_iM_i≡1(mod \ m_i)$ 的一个解，也就是 $M_i$ 的逆元

则方程组的整数解为 $_{i=1}^na_iM_it_i$

证明：

首先解释一下，一般的线性同余方程长这样：a*x≡b (mod m)

它的解有无数个，我们可以将通解表示为 $x=x_0+kt \ (k∈Z)$

而这个通解其实就相当于 $x≡x_0(mod\ t)$

因此所有的线性同余方程组都可以转化为下面这种较为一般的形式

在这里插入图片描述

而孙子定理通过构造法得到了一种特殊情况下（即模数 $m_i$ 两两互质时）的通解，换言之只要能保证模数两两互质则方程组一定有解

证明如下：

将解 $_{i=1}^na_iM_it_i$ 代入原方程组任一方程

$a_1M_1t_1+a_2M_2t_2+\cdot\cdot\cdot+a_iM_it_i+\cdot\cdot\cdot+a_nM_nt_n≡a_i(mod\ m_i)$

上面这个式子显然是成立的

对于 $k \neq = i$ 的项， $a_kM_kt_k≡0(mod\ m_i)$ ，因为 $M_k$ 是 $m_i$ 的倍数

而 $a_iM_it_i≡a_i(mod\ m_i)$ ，因为 $t_i$ 是 $M_i$ 在模 $m_i$ 意义下的逆元， $t_iM_i$ 在模 $m_i$ 意义下等价于1

证毕

方程组的通解可以表示为 $x=∑_{i=1}^na_iM_it_i+km$

中国剩余定理的板子就不放了，毕竟都是些常规操作

需要注意的是中国剩余定理成立的前提是 $m_i$ 互质，不要求 $m_i$ 为素数，所以在求 $t_i$ 时不要使用小费马定理，而应该用扩欧求逆元，在这里放一个扩欧求逆元的板子：

long long exgcd(long long a,long long b,long long &x,long long &y){
   if(a%b==0){x=0;y=1;return b;}
   long long d=exgcd(b,a%b,x,y);
   long long temp=x;
   x=y;y=temp-a/b*y;
   return d;
}

long long inv(long long m,long long mod){ //求m在模mod下的逆元
   long long x,y;
   long long d=exgcd(m,mod,x,y);
   if(d!=1) return -1; //若不互质则无逆元
   long long temp=mod/d;
   return (x%temp+temp)%temp; //返回最小正整数解
}

8.一般的线性同余方程组

中国剩余定理成立的前提是每个方程的模数两两互质，对于其他情况则不适用

可以使用n次扩展欧几里得算法进行求解：

在这里插入图片描述

假设已经求出了前k-1个方程构成的方程组的解 $x$ ， $m$ 为前k-1个方程模数 $m_i$ 的最小公倍数

则前k-1个方程的通解可以表示为 $x + i ? m, i \in Z$

为了使前k-1个方程的解也满足第k个方程，只能从通解中寻找

$x+i*m≡a_k(mod \ m_k)$

只要寻找到满足条件的i即可

对该方程进行转化：

$i*m≡a_k-x \ (mod \ m_k)$

此时只有 $i$ 是未知数，所以这就是一个线性同余方程，用一次扩展欧几里得就可得到它的一个解 $i = t$ ，则 $x^{'}=x+t*m$ 就是前k个方程的一个解

以此类推就能得到整个方程组的解

而如果在某次用扩展欧几里得运算时发现无解，则整个方程无解

；原文链接：https://blog.csdn.net/Qiuker_jl/article/details/112426642
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！

上一篇：软件开发流程与初始软件测试 下一篇：没有了

随机推荐

PostgreSQL存储过程实用脚本(二)：创建函

准备工作——创建用户数据库和模式 ? ? ? ? 在数据库中新建用来学习的数据库 myd...
深渊之刃-Greenplum数据库之拉链表的实现

历史拉链表是一种数据模型，主要是针对数据仓库设计中表存储数据的方式而定义的;...
数据库迁移神器——Flyway

本文转载自微信公众号「Java极客技术」，作者鸭血粉丝。转载本文请联系Java极客...
正则表达式教程之位置匹配详解

本文实例讲述了正则表达式教程之位置匹配。分享给大家供大家参考，具体如下：注...
shiro权限安全框架

shiro权限安全框架什么是shiro 认证和授权为什么要学shiro---安全快速入门shi...
Linux下查看函数被那些函数调用过？

一、问题有个打印log的函数，想知道该函数执行的时候，之前执行了哪些函数? 二...
详解phpstorm2020最新破解方法

推荐阅读： PHPStorm2020.1永久激活及下载更新至2020(推荐) https://www.jb51.ne...
csv文件容错处理方法

如果数据库有特殊字符(换行符，转义符),会导致生成的csv无法正常导入。 val1,val...
HTML中rel属性分析

由于发现有同学在微博转播和收藏这篇文章,所以回头来再审视下这篇随性翻译的文章...
关于程序员生活的一份调查，看看你属于哪

程序员周末都喜欢做什么？在公司加班？在家里加班？看电影？睡觉？程序员都怎么...

【数论】ACM数论知识总结

文章目录

一.质数

1.定义

2.质数的判断

3.质数的筛选

4.质因子分解

5.互质

二.同余

1.模运算

2.定义

3.同余的性质

4.欧拉定理

5.贝祖定理

6.扩展欧几里得

7.中国剩余定理

8.一般的线性同余方程组

推荐图文

好玩的vbs小程序之关机功能

Elasticsearch 分页查询 - 狼爷

Redis数据库学习提高工作效率

30块钱的树莓派跑Unix系统，源码全部开源，香

一文秒懂nodejs中的异步编程

JavaScript 实现继承的几种方式

随机推荐

PostgreSQL存储过程实用脚本(二)：创建函

深渊之刃-Greenplum数据库之拉链表的实现

数据库迁移神器——Flyway

正则表达式教程之位置匹配详解

shiro权限安全框架

Linux下查看函数被那些函数调用过？

详解phpstorm2020最新破解方法

csv文件容错处理方法

HTML中rel属性分析

关于程序员生活的一份调查，看看你属于哪

关于我们