简单数论

前言

本文只要写一些数论以及它的trick

最基础的部分

唯一分解定理

$x=\Pi{p_i^{k_i}}$

公约数

欧几里得求法 $\gcd(a,b)=\gcd(b,a\bmod b)$

辗转相除法 $\gcd(a,b)=\gcd(a-b,b)$ 显然的，小的哪个数应该放在后面，如果小的是 $0$ ，说明没有余数，最大公约数是 $a$

唯一分解定理 $\gcd(a,b)=\Pi{p_i^{\min(k1_i,k2_i)}}$

exgcd

当我们想要$ax+by=k*\gcd(a,b),k\in Z , K \neq 0$的时候，这个时候就需要拓展欧几里得（至于为啥是这么多,看下面的证明）

假设我们现在求出了$d=\gcd(a,b)$，我们先令k=1

那么

$$ax+by=gcd(a,b) \\ \frac{a}{d}x+\frac{b}{d}y=1$$

显然这个时候$d|a,d|b$,根据除法的定义我们可以继续推

$$a_0x+b_0y=1 \\ a_0=q_1b+r_1 \\ b_0=q_2r_1+r_2\\ r_1=q_3r_2+r_3\\$$

这时候根据 gcd ,我们可以求出更多的$r$

这个时候我们可以用 gcd 求出更多的 r 然后找到 r1 ，最后就可以找到一组特解

$(a_0,b_0)$

那么很自然就会想出 exgcd

$ax+by=gcd(a,b)=gcd(b,a\%b)=bx+(a\%b)y$

$bx+(a\%b)y=bx+(a-\lfloor\frac{a}{b}\rfloor)y=ay+bx-b\lfloor\frac{a}{b}\rfloor y\\=ay+b(x-\lfloor\frac{a}{b}\rfloor y)$

但是我们首先要求到 gcd 才能接 x，因此代码就要先注意一下

int exgcd(int a,int b,int &x,int &y)
{
	if(b==0) {x=1;y=0; return a;}
	int t=exgcd(b,a%b,x,y),tmp=x;
	x=y;
	y=tmp-(a/b)*y;
	return t;
}

裴蜀定理

$$ax+by=\gcd(a,b),d=\gcd(a,b) \\ \frac{a}{d}x+\frac{b}{d}y=1$$

如果我们把 $a,b$ 都除以 $d$ ，令 $e=\frac{a}{d},f=\frac{b}{d}$

此时退化成 $\text{exgcd}$ 形式

$$ax+by=\gcd(a,b) \\ ax+by=\gcd(b,a\%b) \\ bx+a\%b=\gcd(b,a\%b) \\ bx+(a-b\lfloor\frac{a}{b}\rfloor)y=\gcd(b,a\%b) \\ bx+ay-b\lfloor\frac{a}{b}\rfloor y=\gcd(b,a\%b) \\ ay+b(x-\lfloor\frac{a}{b}\rfloor y)=\gcd(b,a\%b) \\ ay+b(x-\lfloor\frac{a}{b}\rfloor y)=\gcd(a,b)$$

int exgcd(int a,int b,int &x,int &y)
{
	if(b==0) {x=1;y=0; return a;}
	int t=exgcd(b,a%b,x,y),tmp=x;
	x=y;
	y=tmp-(a/b)*y;
	return t;
}

素数

很基础的性质

唯一分解，哈希，$\varphi(p)=p-1$ 它的同余系最大，因此模数很少哈希冲突。

素数密度 $\frac{x}{\ln(x)}$

判定

由于是基础部分，只介绍三个：（不知道叫啥名字），埃筛，欧拉筛（线性筛？）

bool is_prime(int x)
{
    for(int i=2;i*i<=x;i++) if(x%i==0) return 1;
    return 0;
}

埃筛

int is_notprime[maxn],p[maxn],cnt;

void getprime(int x)
{
    for(int i=2;i<=x;i++)
    {
        if(is_notprime[i]) continue;
        for(int j=2;j*i<=x;j++) is_notprime[i*j]=1;
    }
    for(int i=2;i<=x;i++) if(!is_notprime[i]) p[++cnt]=i;
}

这东西的复杂度好像是 $O(n\log\log n)$，我只能感性认识到一个调和级数和一个素数密度决定了它的复杂度。

线性筛

int is_notprime[maxn],p[maxn],cnt;

void getprime(int x)
{
    for(int i=2;i<=x;i++)
    {
        if(!is_notprime[i]) p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<=x;j++) 
        {
            is_notprime[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}

很显然的是，$i*p[j]$ 一定有一个非 $1$ 的最小因子是 $p[j]$ ，换句话说，$i$ 是这个数的非自身的最大因子。

每个数字的最小质因子只有一个，所以是线性的。

逆元

在模 $p$ 意义下，一个数字 $x$ 的逆元是 $x^{p-1} \pmod p$

那如果 $p$ 是和数呢? 首先我们需要保证这两个数互质，才能求。

$a \times x \equiv 1\pmod p $

$ax+py=1$ 一定有解，因为这是 $\text{exgcd}$

中国剩余定理

$\begin{cases}x\equiv 1(mod~3)\\x\equiv 1(mod~5) \\x\equiv 2(mod~7)\end{cases}$

这个时候先得到

$\begin{cases}x \equiv 1(mod~3)\\x\equiv 1(mod~5) \\x\equiv 1(mod~7)\end{cases}$

考虑特解

$\begin{cases}x \equiv 1(mod~3)\\x\equiv 0(mod~5) \\x\equiv 0(mod~7)\end{cases}$

此时显然可以表示为

令

$s=3,t=5*7$

$M=3*5*7$

$x=1+sa,x=0+tb$

$1+sa=tb,tb-sa=1$

显然也可以写成

$tb+sa=1$

那就可以通过解这个方程得到 s ,然后$ans+=s*(M/s)*1$

然后记得给 ans 取模，并且上面这种解法对任意互质的$p_1,p_2,p_3...p_n$的话，就是中国剩余定理

扩展中国剩余定理

当p不互质的时候，显然存在一组$gcd(a,b)\neq1$，从而无法使用exgcd求解

但是我们可以一直合并，让他最终变成一个同余方程，或者用对每组方程找到p作为lcm来处理，不过比上面难多了

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=100100;

int b[maxn],p[maxn];
int n,m;
int x,y;

int exgcd(int a,int b,int &x,int &y)
{
	if(b==0) {x=1;y=0;  return a;}
	int t=exgcd(b,a%b,x,y),tmp=x;
	x=y;
	y=tmp-(a/b)*y;
	return t;
}

inline int mul(int x,int y,int modp)
{
	int ans=0;
	while(y)
	{
		if(y&1) ans=(ans+x)%modp;
		x=(x+x)%modp;
		y>>=1; 
	}
	return ans;
}


inline int excrt()
{
	int i,j;
	int ans=p[1];
	int nowtot=b[1];
	int lcm=1;
	for(i=2;i<=n;i++)
	{
		int tb,tp,tc;
		tb=nowtot; tp=b[i];
		tc=(p[i]-ans%tp+tp)%tp;
		int gd=exgcd(tb,tp,x,y);
		tc/=gd;
		x=mul(x,tc,tp/gd);
		ans+=x*nowtot;
		nowtot*=(tp/gd);
		ans=((ans%nowtot)+nowtot)%nowtot;
	}
	return (ans%nowtot+nowtot)%nowtot;
}

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n;
	for(i=1;i<=n;i++) cin>>b[i]>>p[i];
	cout<<excrt()<<endl;
}

Lucas

在模一个质数 $p$ 的意义下，询问 $C^{m}_{n} \pmod p$

对质数$p$:

$C_n^m\equiv C_{n\%p}^{m\%p}*C_{n/p}^{m/p}(mod ~p)$

但是为了方便递归理解，也有写成

$Lucas_n^m\equiv Lucas_{n\%p}^{m\%p}*C_{n/p}^{m/p}(mod ~p)$

显然这是个简单到不能再简单的结论，所以我们考虑证明

设$C_a^b$，并且用$p$进制表示$a,b$

$a=a_0+a_1p+a_2p^2+.....+a_np^n$

$b=b_0+b_1p+b_2p^2+.....+b_np^n$

现在我们求一下$(1+x)^p$

其实不用求，显而易见$[1,p-1]$的系数都包含了p的倍数，那么

$(1+x)^p\equiv1+x^p (mod~p)$

这东西有啥用？

回头来看命题

$C_n^m\equiv C_{n\%p}^{m\%p}*C_{n/p}^{m/p}(mod ~p)$

换成数学上的东西

$$C_a^b \equiv C_{a_0}^{b_0}*C_{a_1}^{b_1}*...*C_{a_n}^{b_n}(mod ~p)$$

另外可以发现$（1+x）^a$可以被拆分成

$$(1+x)^a=(1+x)^{a_0}*(1+x)^{a_{1}p}*(1+x)^{a_{2} p_2}*...*((1+x)^{a_{n}p_n})\\ (1+x)^a\equiv(1+x)^{a_0}*(1+x^p)^{a_1}*(1+x^{p^2})^{a_2}*...*(1+x{p^n})^{a_n}(mod~p)$$

根据二项式定理，$C_a^b$就是$x^b$项的系数，两边都拿出上面那个项，就和c与b有关，两边都是b，自然约掉了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

int n,m,p;
int a[200200];

int qpow(int x, int y)
{
	int ans=1;
	x%=p;
	while(y)
	{
		if(y&1) ans=(ans*x)%p;
		x=(x*x)%p; 
		y>>=1;
	}
	return ans;
}

int c(int x,int y)
{
	if(x<y) return 0;
	return ((a[x]*(qpow(a[y],p-2))%p)*qpow(a[x-y],p-2))%p;
}

int getlucas(int x,int y)
{
	if(y==0) return 1;
	return (c(x%p,y%p)*getlucas(x/p,y/p))%p;
}

signed main()
{
	int t;
	register int i,j;
	cin>>t;
	a[0]=1;
	while(t--)
	{
		cin>>n>>m>>p;
		for(i=1;i<=p;i++) a[i]=(a[i-1]*i)%p;
		cout<<getlucas(n+m,n)<<endl;
	} 
} 

扩展卢卡斯

先给p分解质因数，然后用一个中国剩余定理的方程组合并即可。

但是$m!(n-m)!$不保证不与$p^k$互质，所以都要先除掉它的因子，并且$n!$这种式子在$\%p$情况下会出现循环节，以及一部分可以用来递归求解，建议看洛咕的题解（公式太多懒得打）

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

int n,m,p;
int x,y;

int exgcd(int a,int b,int &x,int &y)
{
	if(b==0) {x=1; y=0;return a;}
	int tmp=exgcd(b,a%b,x,y),t=x;
	x=y;
	y=t-a/b*y;
	return tmp;
}

inline int getinv(int a,int p)
{
	exgcd(a,p,x,y);
	return ((x%p)+p)%p;
}

int ksm(int x,int y,int modp)
{
	int ans=1;
	while(y)
	{
		if(y&1) ans=(ans*x)%modp;
		x=(x*x)%modp;
		y>>=1;
	}
	return ans;
}

int f(int x,int pi,int pk)
{
	if(x==0) return 1;
	int p1=1;
	int i,j;
	for(i=1;i<=pk;i++) if(i%pi) p1*=i,p1%=pk;
	p1=ksm(p1,x/pk,pk);
	for(i=1;i<=x%pk;i++) if(i%pi) p1*=i,p1%=pk; 
	return (f(x/pi,pi,pk)*p1)%pk;
}

int getk(int x,int p)
{
	int ans=0;
	while(x) ans+=x/p,x/=p;
	return ans; 
}

inline int c(int n,int m,int pi,int pk)
{
	int ta,tb,tc;
	ta=f(n,pi,pk);
	tb=f(m,pi,pk);
	tc=f(n-m,pi,pk);
	int k=getk(n,pi);
	k-=getk(m,pi);
	k-=getk(n-m,pi);
	int ans=((ta*getinv(tb,pk))%pk)*getinv(tc,pk);
	ans=(ans%pk)*ksm(pi,k,pk);
	ans%=pk;
	return ans;
}

inline int crt(int a,int b)
{
	return getinv(p/b,b)%p*(p/b)%p*(a)%p;
}

inline int exlucas(int n,int m)
{
	int i,tmp=p;
	int ans=0,pk=1;
	int len=sqrt(p)+5;
	for(i=2;i<=len;i++)
	{
		if(tmp%i!=0) continue;
		pk=1;
		while(tmp%i==0) pk*=i,tmp/=i;
		ans=(ans+crt(c(n,m,i,pk),pk))%p; 
	}
	if(tmp!=1) ans=(ans+crt(c(n,m,tmp,tmp),tmp))%p; 
	return ((ans%p)+p)%p;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>p;
	cout<<exlucas(n,m)<<endl; 
}

1.复数

BSGS

带步小步算法

给定一个质数 pp，以及一个整数 bb，一个整数 nn，现在要求你计算一个最小的 $l$，满足$b^l \equiv n \pmod p$。

设$l=k*a-c$

$b^{k*a-c}\equiv n \pmod p$

$b^{k*a}\equiv n*b^c \pmod p$

现在我们需要枚举k和c，所以要找到一个最好的$c$使枚举次数最小

用分块思想想一想啊，显然$a=\sqrt{p}$有最小值。

而且可以保证$[0,p-1]$为一个循环节。

所以找符合条件的$k*\sqrt{p}$就行了

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int max=1001000;

map < int , int > mp;

int p,b,n,m; 

int qpow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1) ans=(ans*x)%p;
		x=(x*x)%p;
		y>>=1;
	}
	return ans;
}

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>p>>b>>n;
	int phi=p;
	m=ceil(sqrt(phi));
	j=n;
	for(i=0;i<=m;i++)
	{
		mp[j]=i;
		j=(j*b)%p;
	} 
	int jmp=qpow(b,m);
	j=jmp;
	for(i=1;i<=m;i++)
	{
		if(mp.count(j)) {cout<<i*m-mp[j]<<endl; return 0;}
		j=(j*jmp)%p;
	}
	cout<<"no solution"<<endl;
	return 0;
}

欧拉定理

欧拉函数

$\phi(x)$或者$\varphi(x)$表示$1\to x$中与$x$互质的正整数个数

显然$\phi(p)=p-1,p$为质数

从这里我们可以推导出

$\phi(p^e)=(p-1)*p^{e-1}$

根据唯一分解定理，有

$$\begin{align} P&=k_1^{e_1}*p_2^{e_2}*...*p_n^{e_n}\\ \phi(P)&=\phi(p_1^{e_1})*\phi(p_2^{e_2})*...*\phi(p_n^{e_n})\\ &= \Pi_{i=1}^{n} (p_i-1)*(p_i^{e_i-1}) \\ &= \Pi_{i=1}^{n} (1-\frac{1}{p_i})*(p_i^{e_i}) \\ &= n*\Pi_{i=1}^{n} (1-\frac{1}{p_i}) \end{align}$$

我们就可以用这种方式求出$\phi(n)$

void phi_table(int n)
{	
	phi[1]=1;	
	for(int i=2;i<=n;i++) if(!phi[i])//如果i的欧拉函数没有计算则计算	   
	for(int j=i;j<=n;j+=i)//计算素数i及其倍数的欧拉函数，所以进入第二层循环的i都是素因子   
	{	
		if(!phi[j])phi[j]=j;//如果j的欧拉函数没有计算则先赋值为j(由欧拉函数知)
		phi[j]=phi[j]/i*(i-1);//累乘得欧拉函数
	}
}

对于单个n，还有一个$O(\sqrt{N})$的方法

signed main()
{
	ios::sync_with_stdio(false);
	register int i;
	cin>>m;
	phi=m;
	for(i=2;i*i<=m;i++) 
	if(tmp%i==0){phi-=phi/i; while(tmp%i==0) tmp/=i;}
	if(tmp!=1) phi-=phi/tmp;
}

欧拉定理

$a^{\phi(m)}\equiv1 (~mod~m),a\perp m$

证明：证明这个数有$\phi$个不同的同余系，并且一一对应（证明同$a^{p-1}$在模$p$意义下为$a$的逆元）

扩展欧拉定理

先咕一下证明（两年了）

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

int a,b,m,phi,tmp,bj;

inline void qread(int &x)
{
	x=0;
	static char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) {x=x*10+c-'0'; if(x>=phi) x%=phi,bj=1; c=getchar();}
	return ;
}

inline int ksm(int x,int y,int modp)
{
	int ans=1;
	while(y)
	{
		if(y&1) ans=(ans*x)%modp;
		x=(x*x)%modp;
		y>>=1;
	}
	return ans;
}

signed main()
{
	//ios::sync_with_stdio(false);
	register int i,j;
	cin>>a>>m;
	phi=m; tmp=m;
	for(i=2;i*i<=m;i++) 
	if(tmp%i==0){phi-=phi/i; while(tmp%i==0) tmp/=i;}
	if(tmp!=1) phi-=phi/tmp;
	qread(b);
	cout<<ksm(a,bj?b+phi:b,m);
}