数论基础知识(1)

声明:

这是一篇面对萌新的友好文章,大佬就没必要看了(因为大都是基础

如果有的写错了,望指正; 如果有的写的不清楚, 望周知; 感谢!

参考课件来自PoPoQQQ(虽然我不认识他)和网络博客,讲授来自Accelerator & ollie同学

整理就是我这个juruo做的

$ Latex $ 炸了请告诉我

总结(建议看完之后在看看

重点:https://www.cnblogs.com/tyner/p/11360204.html#scroller-2中的线性筛

https://www.cnblogs.com/tyner/p/11360204.html#scroller-7中的快速幂

https://www.cnblogs.com/tyner/p/11360204.html#scroller-11

https://www.cnblogs.com/tyner/p/11360204.html#scroller-20

https://www.cnblogs.com/tyner/p/11360204.html#scroller-23

https://www.cnblogs.com/tyner/p/11360204.html#scroller-23求逆元

https://www.cnblogs.com/tyner/p/11360204.html#scroller-18线性筛欧拉函数

https://www.cnblogs.com/tyner/p/11360204.html#scroller-22扩展欧拉定理

共五组例题

质数的筛法和应用

  1. 埃拉托斯特尼筛法

    基本思想:素数的倍数一定不是素数

int tmp = sqrt(n+0.5);//说是解决精度问题,不懂... 
for(int i = 2; i <= tmp; i++) if(!notp[i]) //i*i<n //1看题目考虑 
    for(int j = i*i; j <= n; j+=i) {//没有必要从j*2, 因为在i=2的时候已经被筛掉了 
    notp[j] = 1;
   }
  1. 线性筛

    原理:初始时,假设全部都是素数,当找到一个素数时,显然这个素数乘上另外一个数之后都是合数,把这些合数都筛掉,即算法名字的由来。

   int not_prime[N] = {1, 1};
   int prime[N], tot;
   
   void L_S(){
   	for(int i = 2; i <= n; i++) {
   		if(!not_prime[i]) //i是从小到大枚举的,所以在这之前已经知道not_prime[i]的值,即知道i是否为质数
   			prime[++tot] = i;//加入素数表
   		for(int j = 1; j <= tot && i*prime[j] <= n; j++) {// 注意j是从小到达枚举的,也就是说prime[j]从小到大
   			not_prime[i*prime[j]] = 1;//所以,此时,i*prime[j]的最小质因数为prime[j],即它被prime[j]筛掉了 
   			if(i%prime[j] == 0) break;//在这之后,i*prime[j+1]的最小质因数在i的唯一分解式内,而不是prime[j+1],所以break
   		}
   	}	
   }
  1. 素数应用

    • 用来取模
    • 用来装 B

一例题:P2312 解方程

gcd和lcm

gcd(x,y),简记为(x,y),表示两个数的最大公约数

lcm(x,y),简记为[x,y],表示两个数的最小公倍数

设$ x=∏pi^{ai} $ ,$y=∏pi^{bi} $

那么$ (x,y)=∏pi^{min(ai,bi)} $ $ [x,y]=∏pi^{max(ai,bi)} $

由于min(ai,bi)+max(ai,bi)=ai+bi,故有$ (x,y)* [x,y] = x *y $

注意: 即使知道公式,也不能直接套(lcm(a, b) = a * b/gcd(a, b)) 因为a *b可能溢出!! 正确的姿势是先除后乘
a/gcd(a,b) * b。 这样一来,只要题面上保证最终结果在int范围内,就不会出错(没有保证的, 或者是不确定的,自己就加个(long long)把)。

$ gcd(a,b,c)=gcd(gcd(a,b),c) $

辗转相除法

用途:求两数Gcd

算法流程:不断用大数模去小数直到其中一方为0,则另一方为两数最大公约数。即:

[gcd(a,b)=gcd(b,a mod b) ,b≠0 ]

正确性证明:Gcd(a,b)=Gcd(a,a+b) ※←记住这个结论,很有用

(a < b),以上等式显然成立(你这要是不会我也没办法)#1

(a geq b), 设(a = q *b + r,0leq r<b), 即r=a%b 。对于(a)(b)的任意公约数(d),因为(d|a)(ps:这个符号的意思是d是a的约数),(d|b),所以(d|(q * b)), 可得(d|(a-q*b))#2,即(d|r)(d)也是(r)的约数。反之亦成立。所以,(a)(b)的公约数集合和(b)(a mod b)的公约数集合相同,他们的最大公约数自然也相同。

    证毕

~#1解释:(gcd(10,20)=gcd(20,10mod20)=gcd(20,10)) [竟然看这个]

~#2解释:为什么?因为(d|a),(d|b)可以写成(a=k1*d,q*b=k2*d),相减得(a-q*b=(k1-k2)*d)即是d的倍数

复杂度:O(logn)

复杂度证明自行百度

例题见:gcd套路变换https://www.cnblogs.com/tyner/p/11853212.html#scroller-0

同余公式

注: (a equiv b(mod p)) 含义是“a和b关于模p同余”, 即$ a mod p = b mod p $。 它的充要条件是: a-b是p的整数倍
(a+b)%p = (a%p + b%p) %p

(a-b)%p = (a%p - b%p) %p

(a* b)%p = (int)( (LL) (a%p) * (b%p) % p )

推论:a^b %p = (a%p)^b %p

除法怎么办???

看下面的乘法逆元

大整数取模

输入正整数a, p, 求a % p, $a <= 10^{100} $, $ p <= 10^9 $ :
把大整数写成从左到右的形式:

cin>>a>>p;
int len = a.length();
int ans = 0;
for(int i = 0; i < len; i++) 
	ans = (int)(((long long)ans*10 + a[i] - '0') % p);
printf("%d", ans);

幂取模

(下面的欧拉定理里的ex欧拉也有, 这里就写一写刘汝佳书上的
输入正整数a, n, m, 求 $ a^n mod m $ 的值, a,n,m <= $ 10^9 $
优化正常方法, 分治思想:

int pow_mod(int a, int n, int m) {
    if(n == 0) return 1;
    int x = pow_mod(a, n/2, m);
    long long ans = (long long) x * x % m;
    if(n % 2 == 1) ans = ans * a % m;
    return (int)ans;
}

注意!! 做模板题的时候发现了一个bug
就是这个代码在n=0是直接返回1, 如果m=1的话,结果就不对了,所以需要特判一下,其他的情况都是对的吧

也可以不用分治,快速幂也行:(不知道写的对不对,建议开longlong)

int ksm(int a, int b, int p) {
	int res = 1;
	while(b) {
		if(b&1) res = (long long)res*a%p;
		b >>= 1;
		a = (long long)a*a%p;
	}
	return res;
}

这个代码也注意一下,b=0且p=1时,返回的是1,应该返回0
解决方法:1.可以写一个特判 2. 可以把最后一个return改成:return res%p

模线性方程

给出正整数a, b, p, 解方程(a*x equiv b pmod p)

a*x-b是p的整数倍, 我们设这个整数为y, 那么(a *x - p *y = b)
这个和下面"求乘法逆元->扩展欧几里得(exgcd->直线上的点,求逆元"是一样的, 建议忽略此处,等看过那个之后再回来

唯一要说明的是,若x是方程的解, 那么满足(x equiv z pmod p)的其他整数z, 显然根据同余的定义,z也是方程的解。 因此谈到同余方程的解时, 其实指的是应该同余等价类(摘自紫书)

求乘法逆元

定义:对于任意x∈[1,p),若$ (x,p)=1 $,则存在唯一的正整数 $ inv[x]∈[1,p) $ 满足$ x*inv[x]≡1(mod p)$,我们称inv[x]x在模p意义下的逆元

$ a/x (mod p) = a* 1/x (mod p) = a* inv[x] (mod p) $

这说明,当我们在$ mod p $意义下需要除掉x的时候,我们只需要乘上x的逆元就行了。

扩展欧几里得(exgcd

用途:求出方程ax+by=gcd(a,b)的一组解,其中a和b已知,x和y未知

引理:裴蜀定理,一定存在(ax+by=gcd(a,b))的整数解

    乱证严格的证明:

(b=0)时,(gcd(a,b)=a),显然存在一对整数解(x=1,y=0)
    (gcd(10,0)=10)
(b eq0)
      设(ax1+by1=gcd(a,b)=gcd(b,a mod b)=bx2+(amod b)y2)

      又因 (amod b=a-a/b*b)

      则 (ax1+by1=bx2+(a-a/b*b)y2)

      (ax1+by1=bx2+ay2-a/b*by2)

     //合并同类型得

      (ax1+by1=ay2+b(x2-a/b*y2))

      解得 (x1=y2 , y1=x2-a/b*y2)

      因为当 (b=0) 时存在 (x , y) 为最后一组解

      而每一组的解可根据后一组得到

      所以第一组的解 (x , y) 必然存在

于是我们有$ x=y2,y=x2-a/b* y2 $ 满足$ a* x+b* y=gcd(a,b) $

补一下:裴蜀定理可以扩展到多个数的情况:
https://www.luogu.org/problem/P4549

求逆元

方法:a *x≡1(mod p)即$ a* x+p* y=1 $,用Exgcd求出任意一个x后mod p即可。
(根据逆元定义,此时x即为a关于模p的逆
什么时候x存在呢? a* x+p* y=1方程要有解。 这样, 1就必须是gcd(a, p)的倍数,因此,a和p必须互质, 在满足这个条件下, (a*x equiv 1 pmod p) 只有唯一解, 否则,该方程无解。

int exgcd(int a, int b, int& x, int& y) {
	if(!b) {
		x = 1;
		y = 0;
		return a;
	} 
	int d = exgcd(b, a%b, y, x);//此时算的x=y1, y=x1;
	y -= (a/b)*x;//y应该为 x1-(a/b)*y1 
	return d;
}

int main() {
	int x, y;
	scanf("%d%d",&a, &b);
	exgcd(a, b, x, y);
	if(x<0) x = (x%b)+b;//如果是负的,要先转正(先%再+保证转正
        //对于网上这里x<0时直接+b,是因为我们上面让了|x|+|y|最小,所以+b就“成功转正了”
        //其它的时候注意对负数取模时要先%再+再取%
	printf("%d",x%b);//得到的是任意一个x, 所以它可能大于b
}

//没有return的时候注意写if和elseif里面写return

直线上的点: 求ax+by=m上有多少整点(x,y)

设g=gcd(a,b),(注:g==0可以特判一下,以下都是g!=0的情况), ax+by=g的一组解是(x0, y0) 。 当m是g的倍数时(g可以由exgcd顺便返回),有解, 为(x0* c/g, y0* c/g) (自己化一下);反之,无解。 证明如下

方程 (ax + by = m)有解的必要条件是 (m mod gcd(a,b) = 0)

由最大公因数的定义,可知 (a)(gcd(a,b)) 的倍数,且 (b)(gcd(a,b)) 的倍数,

(x,y) 都是整数,就确定了 (ax + by)(gcd(a,b)) 的倍数,

因为 (m = ax + by),所以 (m) 必须是 (gcd(a,b)) 的倍数,

那么 (m mod gcd(a,b) = 0)

欧拉定理

欧拉函数

定义:

欧拉函数φ(n)表示[1,n]范围内与n互质的数的个数。

性质:
  1. φ(1)=1

  2. $ φ(p)=p-1 $(p为质数, 即费马小定理

    证明:质数定义

  3. (varphi(p^{k}) = (p-1)*p^{k-1} = varphi(p)*p^{k-1})(p为质数

    证明:我们知道,在 1~p 之间与 p 不互质的数共1个,在 1~2×p 之间与 p 不互质的数共2个……在1~p^(k−1)×p 之间有 p^(k−1) 个。所以在 1~p^k 之间与 p 不互质的数有 p^(k−1) 个,互质的那就是p^(k)−p^(k−1),故φ(p^k)= p^k−p^(k−1),即第二个式子。然后提取公因数 p^(k−1) 得到第三个式子。结合性质2得到第四个式子。

  4. 设$ n=prod_{i = 1}^{k}p_i^{ai} $,那么

    (φ(n) = Π {φ(pi^{ai})} = Π {(pi-1) * pi^{ai-1}} = n*prod(1- frac{1}{pi}))

    证明:由于欧拉函数有积性,(φ(ab)=φ(a)φ(b)),所以有

    [varphi(n)=prod_{i=1}^{k}varphi(p_{i}^{ri}) ]

    结合性质2的第三个式子,我们可以得到第三个式子。对于第三个式子,我们提取一个公因子p,得到

    [prod_{i=1}^{k}p_{i}^{ri}*(1-frac{1}{pi})=(prod_{i=1}^{k}p^{ri})*(prod_{i=1}^{k}(1-frac{1}{pi}))=n*prod_{i=1}^{k}(1-frac{1}{pi}) ]

    得证。

例:φ(50)=φ(2* 25)=50* (1-1/2)* (1-1/5)= 20

扩展性质(不证明
  1. (a,b)不互质,那么(φ(ab))等于什么呢?

结论:令(d=gcd(a,b)),则

[varphi(ab)=frac{varphi(a)varphi(b)d}{varphi(d)} ]

  1. 对于任意正整数(n)(φ(n))(n)有什么样的关系?

结论:

[n=sum_{d|n}varphi(d) ]

欧拉函数求法
  1. 单独求φ:分解质因数 O(√n)(安利使用最下方的线性求phi

    原理:质因子分解(基本性质3)。每次找到一个素因子,之后把它”除干净“,即可保证找的因子全部都为素数(这个比较容易理解,从2开始进行循环,删除二的所有倍数,因为含有倍数,则必定不是素数,从而确保下次循环所选的数必定为素数,额…若仍不理解,可以自己打表看一下,而事实也确实如此)。

int euler_phi(int n) {
	int m = (int)sqrt(n+0.5);//(还是说解决精度问题//这里都行吧
	int ans =  n;
	for(int i = 2; i <= m; i++) if(n%i == 0) {
		ans = ans / i * (i-1);
		while(n%i == 0) n /= i;
	}
	if(n > 1) ans = ans / n * (n-1);//还要看n有没有大于sqrt(n)的质因数 
}
  1. 线性筛法

    由于欧拉函数有积性,所以结合扩展性质1:

    (d=gcd(a,b)),则

    [varphi(ab)=frac{varphi(a)varphi(b)d}{varphi(d)} ]

    我们可以通过线性筛质数,在筛出合数 (x * pri[j]) 的同时计算出 (φ( x*pri[j] ))。(注:(pri[j]) 为已经筛出来的质数,见上面的线性筛 )

    不过,需要分2种情况计算:

    1. (x)(pri[j]) 互质.

      这种情况比较简单。由于(d=1)(φ(d)=1),所以

    [varphi(x*pri_{j})=varphi(x)*varphi(pri_{j}) ]

    直接计算即可(也可根据下面的积性函数定义

    1. (x)(pri[j]) 不互质.

      这种情况下,(x) 只可能是 (pri[j]) 的倍数(x大于(pri[j])),故(d = gcd( x, pri[j] ) = pri[j]),根据扩1,所以:

    [varphi(x*pri_{j})=frac{varphi(x)varphi(pri_{j})pri_{j}}{varphi(pri_{j})}=varphi(x)*pri_{j} ]

    带入计算即可

   int not_prime[N] = {1, 1};
   int prime[N], tot;
   int n, m;
   int phi[N];
   
   void L_S(){
        phi[1] = 1;
   	for(int i = 2; i <= n; i++) {
   		if(!not_prime[i]) {
   			prime[++tot] = i;
   			phi[i] = i - 1;//基本性质2:费马小定理 
   		}
   		for(int j = 1; j <= tot && i*prime[j] <= n; j++) {
   			not_prime[i*prime[j]] = 1;
   			if(i % prime[j] == 0) {//如果i是prime的倍数->i与prime[j]不互质 
   				phi[i*prime[j]] = phi[i]*prime[j];
   				break;
   			}
   			phi[i*prime[j]] = phi[i]*(prime[j]-1);//互质的时候,左边=phi[i]*phi[prime[j]],即=右边的
   		}
   	}
   }

性质:**积性函数 **

互质的数的和

补一个[1,n]范围内 与n互质的数 的和
$(φ(n)*n )/ 2 $

欧拉定理

对于任意正整数a,p满足(a,p)=1 (即a,p 互质),有:

$ a^{φ(p)}≡1(mod p)$

特别地,若p为质数则为费马小定理

$ a^{p-1}≡1(mod p)$

推论:$ a*a^{φ(p)-1}≡1(mod p)$

回顾乘法逆元的定义(a^{φ(p)-1})即为a在模p意义下的逆元

//用一个快速幂+单个求phi即可求得

//当p为质数时(即费马小定理),更方便,只需一个快速幂即可

线性求[1, n]所有数对质数p的逆元

当p是质数的时候我们可以线性预处理出[1,n]之间所有数在模p意义下的逆元

设p=kx+b,那么有:

$ kx+b≡0 (mod p) $

$ b* inv[b]* inv[x] ≡ -kx* inv[b]* inv[x] (mod p) $

$ inv[x] ≡ -k*inv[b] (mod p) $

$ inv[x] ≡ (p-k)inv[b] (mod p) //转正 $

故有$ inv[x] = (p-p/x)*inv[pmod x]mod p $

而p%x<x,因此我们从1~n循环就可以求出1~n中所有数关于p的逆元:

[x^{-1}equiv(p-left lfloorfrac{p}{x} ight floor)*(p\,mod\,x)^{-1}pmod{p} ]

注意溢出

inv[1]=1;
for(i = 2; i <= n; i ++)
{
    inv[i]=(ll)(p-p/i)*inv[p%i]%p;
}

阶乘求逆元

补一个: 求(n!^{-1} pmod p), p为质数:

设fac[ni]为 (ni!), ifac[ni] 为$ (ni !)^{-1}$

先递推预处理fac[]

再有$ ifac[n] = (n!)^{φ(p)-1}$, 且p为质数

得,$ ifac[n] = (n!)^{p-2}$

又: $ ifac[n-1] = ifac[n] * n $

所以我们for(n-1 —> 1) 求出[1~n-1]的ifac即可

二例题

P2613 【模板】有理数取余

P5431 【模板】乘法逆元2

扩展欧拉定理

总前提:当 (a , p ∈ Z) 时,考虑a,p是否互质,有:

(a^bequiv a^{b mod φ(p)}pmod p) [a ,p 互质]

$a^bpmod p ,,equiv $ [a,p不需要互质]

  1. $ a^b [b<p] pmod p$
  2. (a^{bmodφ(p)+φ(p)} [b geq p] pmod p)

要求什么什么指数次幂,或在模一个数下的带幂的数的输入用这个做(有点绕口,建议看题:

三例题P5091 【模板】欧拉定理

P4139 上帝与集合的正确用法

(我以为最重要的)逆元求法的使用场合

四例题https://www.luogu.org/problem/P3811

一般来说如果模数是素数并且需要用到1~n所有数的逆元的时候线性预处理没的说

其他情况一般视p是否是素数而定

如果p是素数,一般用欧拉定理,一个快速幂搞定: p是素数&费马小定理,所以a对p的逆即为 $ a^{p-2} pmod p$, 运用一个pow_mod(a, p-2, p)或快速幂即可

如果p不是素数,欧拉定理求φ(p)就比较慢了,一般用Exgcd

积性函数

若数论函数f不恒等于0,且当gcd(m,n)=1时,有f(mn)=f(m)f(n),则f叫做积性函数。若一个积性函数对于∀m,n均有f(mn)=f(m)f(n),则叫做完全积性函数。

积性函数可以通过以下两种方式快速计算

1、分解质因数

2、线性筛法

分解质因数:$F(n)=F(Πpi^{ai})=ΠF(pi^{ai}) $

F(p^a)通常比较好求

那么我们就可以在O(√n)的时间复杂度求出F(n)

下面是线性筛法的做法

线性筛法

用途:在O(n)的时间内筛出[1,n]范围内所有的素数,顺便筛出[1,n]范围内所有数的φ值/μ值/某积性函数值

方法如下:

枚举i=2..n,如果i没有被标记为“不是素数”就把i加入数组

无论i是不是素数,枚举已经筛到的每一个素数p,将i*p标记为“不是素数”

如果i是p的倍数,退出循环

这样可以保证一个数只会被最小素因子筛到一次(想想唯一分解定律),因此复杂度为O(n)

如果要求函数值就顺便讨论讨论计算一下值就行了(如下

(下面的函数不求φ值,只筛素数时,去掉phi[]即可)

以欧拉函数为例讲解一下线性筛法的实现

int not_prime[N] = {1, 1};
int prime[N], tot;
int phi[N];
void Linear_Shaker() {
	phi[1] = 1;
	for(int i = 2; i <= n; i++) {
		if(!not_prime[i]) {
			prime[++tot] = i;
			phi[i] = i-1;//费马小定理
		} 
		for(int j = 1; j <= tot && i*prime[j] <= n; j++) {
			not_prime[i*prime[j]] = 1;
			if(i % prime[j] == 0) {//如果i是prime的倍数->i是合数,i与prime[j]不互质了
				phi[i*prime[j]] = phi[i]*prime[j];//想想公式,i*prime[j]之后对phi的贡献乘以了个prime[j]
				break;//保证被最小的质因子筛掉一次(因为我们保证prime[j]从小到大
			}
			phi[i*prime[j]] = phi[i]*(prime[j]-1);//积型函数公式,费马小定理
		}
	}
}

安利

相关数学证明

积性函数与筛法

oy同学的博客

原文地址:https://www.cnblogs.com/tyner/p/11360204.html