初等数论笔记-算法竞赛相关 Ⅰ

Mathematice / Elementary Numeber Theory
字数统计: 1.8k   |   阅读时长≈ 10 分钟

去年7月开始，陆续写到11月，在电脑本地整理了一些算法竞赛相关的数学笔记，现在搭建了博客后会陆续上传到博客上QwQ

初等数论相关的笔记目前推送了四篇（Ⅱ，Ⅲ，Ⅳ），有时间的话后面会继续推送组合数学、计算几何相关的内容。

Inverse

扩展欧几里得求逆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ll exgcd(ll a,ll b,ll &x,ll &y){
	ll d=a;
	if(b){
		d=exgcd(b,a%b,y,x);
		y-=(a/b)*x;
	} else{
		x=1;y=0;
	}
	return d;
}
inline ll inv(ll a,ll mod){
	ll x,y;
	if(exgcd(a,mod,x,y)!=1)
		return -1;
	return (x%mod+mod)%mod;
}

快速幂求逆

1
2
3
4
5
6
7
8
9
10
11
inline ll qpow(ll b, ll p, ll mod){
	ll r=1;
	while(p){
		if(p&1)
		r=r*b%mod;
		b=b*b%mod;
		p>>=1;
	}
	return r;
}
inline ll inv(ll a,ll mod){ return qpow(a,mod-2,mod); }

欧拉函数求逆

若aa和mm互素： aϕ(m)≡1(mod  m)  ⟹  a⋅aϕ(m)−1≡1(mod  m)a^{\phi(m)}\equiv 1(mod \; m)\implies a·a^{\phi(m)-1}\equiv1(mod \; m)

线性逆元

对于质数pp，有

ki+r≡0(mod  p)kr−1+i−1≡0(mod  p)i−1≡p−kr−1(mod  p)i−1≡p−⌊pi⌋⋅(p%i)−1(mod  p)inv[i]=p−⌊pi⌋⋅inv[p%i]  %p\begin{aligned} ki+r&\equiv0(mod\;p)\\ kr^{-1}+i^{-1}&\equiv0(mod\;p)\\ i^{-1} &\equiv p-kr^{-1}(mod\;p)\\ i^{-1} &\equiv p-\lfloor\frac{p}{i}\rfloor·(p\%i)^{-1}(mod\;p)\\ inv[i]&=p-\lfloor\frac{p}{i}\rfloor·inv[p\%i]\;\%p \end{aligned}

其中，inv[1]=1inv[1]=1​

Euler Sieve

筛质数

1
2
3
4
5
6
7
8
9
10
11
12
void pre(int n){
	for(int i=2;i<=n;i++){
		if(!vis[i])
			pri[++tot]=i;
		for(int j=1;j<=tot&&pri[j]*i<=n;j++){
			int cur=pri[j]*i;
			vis[cur]=1;
			if(i%pri[j]==0)
				break;
		}
	}
}

筛简单的积性函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//fac[]因子个数，num[]质因子个数
void pre(int x){
	fac[1]=1;
	for(int i=2;i<=x;i++){
		if(!vis[i])
			pri[++tot]=i, num[i]=1, fac[i]=2;
		for(int j=1;j<=tot&&i*pri[j]<=x;j++){
			vis[i*pri[j]]=1;
			if(i%pri[j]==0){
				num[i*pri[j]]=num[i]+1;
				fac[i*pri[j]]=fac[i]/(num[i]+1)*(num[i]+2);
				break;
			}
			fac[i*pri[j]]=fac[i]*2;
			num[i*pri[j]]=1;
		}
	}
}

CRT & exCRT

CRT

对于方程组

{x≡b1(mod  a1)x≡b2(mod  a2)......x≡bn(mod  an)\begin{cases} x \equiv b_1(mod\;a_1) \\ x \equiv b_2(mod\;a_2) \\ ...... \\ x \equiv b_n(mod\;a_n) \end{cases}

有解的充分条件是模数两两互质

在aia_i两两互质的前提条件下可引入中国剩余定理CRT，通过构造可得到该线性同余方程组的通解。

x≡∑i=1nbiri[ri]−1∣ai(mod  p)x\equiv\sum_{i=1}^{n}b_ir_i[r_i]^{-1}|_{a_i}(mod\;p) 

1
2
3
4
5
6
7
8
9
10
11
ll CRT(ll a[],ll b[],ll n){
	// a是模数数组，b是余数数组，n是数组长度
	ll p=1,x=0;
	for(int i=0;i<n;++i)
		p*=a[i];
	for(int i=0;i<n;++i){
		ll r=p/a[i];
		x+=(b[i]*r*inv(r,a[i]))%p;
	}
	return x%p;
}

exCRT

当模数两两不互质时，解线性同余方程组，可用到exCRT。

exCRT算法思想：

  1. 读入所有方程组。
  2. 弹出两个方程，先判断有没有解。
    - 无解：异常
    - 有解：合并成同一个方程，然后压进方程组
  3. 执行上述步骤2，直到只剩下一个方程。由这个方程得到解系。

在步骤2中，对于两个方程

{x≡r1(mod  m1)x≡r2(mod  m2)\begin{cases} x \equiv r_1(mod\;m_1) \\ x \equiv r_2(mod\;m_2) \\ \end{cases}

等价于a=k1m1+r1=k2m2+r2  ⟹  k1m1=(r2−r1)+k2m2a=k_1m_1+r_1=k_2m_2+r_2\implies k_1m_1=(r_2-r_1)+k_2m_2​

当gcd(m1,m2)∤(r2−r1)gcd(m_1,m_2)\nmid (r_2-r_1)时该方程无解

有k1m1=r2−r1+k2m2  ⟹  k1m1d=r2−r1d+k2m2dk_1m_1=r_2-r_1+k_2m_2\implies k_1\frac{m_1}{d}=\frac{r_2-r_1}{d}+k_2\frac{m_2}{d}，其中d=gcd(m1,m2)d=gcd(m_1,m_2)​

得到k1m1d≡r2−r1d(mod  m2d)k_1\frac{m_1}{d}\equiv\frac{r_2-r_1}{d}(mod\;\frac{m_2}{d})​

  ⟹  k1≡r2−r1d⋅[m1d]−1(mod  m2d)\implies k_1\equiv\frac{r_2-r_1}{d}·[\frac{m_1}{d}]^{-1}(mod\;\frac{m_2}{d})​​

即k1=r2−r1d⋅[m1d]−1∣m2d+t⋅m2dk_1=\frac{r_2-r_1}{d}·[\frac{m_1}{d}]^{-1}|_{\frac{m_2}{d}}+t·\frac{m_2}{d}​，

得到

a=k1m1+r1=r1+m1⋅(r2−r1d⋅[m1d]−1∣m2d+t⋅m2d)a=k_1m_1+r_1=r_1+m_1·(\frac{r_2-r_1}{d}·[\frac{m_1}{d}]^{-1}|_{\frac{m_2}{d}}+t·\frac{m_2}{d})​

  ⟹  a=r1+m1r2−r1d⋅[m1d]−1∣m2d+t⋅m1⋅m2d\implies a=r_1+m_1\frac{r_2-r_1}{d}·[\frac{m_1}{d}]^{-1}|_{\frac{m_2}{d}}+t·\frac{m_1·m_2}{d}

即a=r1+m1r2−r1d⋅[m1d]−1∣m2d  mod  m1⋅m2da=r_1+m_1\frac{r_2-r_1}{d}·[\frac{m_1}{d}]^{-1}|_{\frac{m_2}{d}} \;mod\;\frac{m_1·m_2}{d}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll exCRT(int n,ll rem[],ll mod[]){
	ll ans=rem[1],M=mod[1],x,y,c,gcd;
	for(int i=2;i<=n;i++){
		c=(rem[i]-ans%mod[i]+mod[i])%mod[i]; 
		exgcd(M,mod[i],x,y,gcd);
		if(c%gcd) 
			return -1;
		x=mul(x,c/gcd,mod[i]/gcd);
		ans+=x*M; 
		M*=mod[i]/gcd;
		ans=(ans%M+M)%M;
	}
	return ans;
}

Euler & exEuler

欧拉函数

积性函数ϕ(m)=m(1−1p1)(1−1p2)...(1−1pm)\phi(m)=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_m})​​

对于素数pp显然易得

{ϕ(p)=p−1ϕ(i∗p)=p∗ϕ(i)      (i  mod  p=0)ϕ(i∗p)=(p−1)⋅ϕ(i)      (i  mod≠p)\begin{cases} \phi(p)=p-1\\ \phi(i*p)=p*\phi(i)\;\;\;(i\;mod\;p=0)\\ \phi(i*p)=(p-1)·\phi(i)\;\;\;(i\;mod\neq p) \end{cases}

筛欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void pre(int n=1e7){
	//	mle的话把vis改成phi
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			pri[++tot]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=tot&&pri[j]*i<=n;j++){
			int cur=pri[j]*i;
			vis[cur]=1;
			if(i%pri[j]==0){
				phi[cur]=pri[j]*phi[i];
				break;
			} else{
				phi[cur]=(pri[j]-1)*phi[i];
			}
		}
	}
	return ;
}

根号求单个

1
2
3
4
5
6
7
8
9
10
11
ll euler(ll x){
	ll ans=x;
	for(int i=2;i*i<=x;++i){
		if(x%i==0){
			ans=ans-ans/i;
			while(x%i==0) x/=i;
		}
	}
	if(x>1) ans=ans-ans/x;
	return ans;
}

欧拉定理

设mm是一个正整数，a是一个整数且(a,m)=1(a,m)=1，那么aϕ(m)≡1(mod  m)a^{\phi(m)}\equiv 1(mod \; m).

即若gcd(a,m)=1gcd(a,m)=1​​，则有gcd(aϕ(m),m)=1  ⟹  ab≡ab%ϕ(m)(mod  m)gcd(a^{\phi(m)},m)=1\implies a^b\equiv a^{b\%\phi (m)}(mod\;m)​

扩展欧拉定理

当gcd(a,m)≠1gcd(a,m)\neq1时引入exEuler

{ab≡ab%ϕ(m)(mod  m),  gcd(a,m)=1ab≡ab(mod  m)，        gcd(a,m)≠1，b<ϕ(m)ab≡a(b%ϕ(m))+ϕ(m)(mod  m)，  gcd(a,m)≠1，b≥ϕ(m)\begin{cases} a^b\equiv a^{b\%\phi (m)}(mod\;m), \;\quad\qquad gcd(a,m)=1\\ a^b\equiv a^b(mod\;m)，\qquad\;\;\;\; \qquad gcd(a,m)\neq1，b<\phi(m)\\ a^b\equiv a^{(b\%\phi (m))+\phi(m)}(mod\;m)，\;gcd(a,m)\neq1，b\geq\phi(m) \end{cases}

打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022-2023 JingyiQu
  • 访问人数: | 浏览次数:

如果这篇博客帮助到你，可以请我喝一杯咖啡~

支付宝
微信