一.斐蜀定理

(1).内容：

若

a,b \in \mathbb{Z}

且不全为0，则

\forall x,y \in \mathbb{Z}

，满足

\gcd(a,b) \mid ax+by

，

\exists x,y \in \mathbb{Z}

，使得

ax+by=\gcd(a,b)

。

(2).推广

1.逆定理

若

a,b \in \mathbb{Z}

且不全为0，若

d>0

，且

d \mid a,d \mid b

，

\exists x,y \in \mathbb{Z}

，使得

ax+by=d

，则

d=\gcd(a,b)

。

2.扩展

显然可以扩展到多个整数。

(3).进一步结论

对于

a,b \in \mathbb{N},n \in \mathbb{Z}

且

a \perp b

，有以下几个结论：

记 $C=ab-a-b$ ，显然有 $C$ 为奇数。
可得

\begin{cases} t=C,\forall x,y \in \mathbb{N}, ax+by \ne t\\ t>C,\exists x,y \in \mathbb{N}, ax+by = t \end{cases}

进而可得：对于方程 $ax+by=c$ ，在 $[0,C]$ 中，恰有 $\frac{(a-1)(b-1)}{2}$ 个 $c$ 满足条件，即 $\forall n \in \mathbb{N},n,C-n$ 中有且只一个满足条件。

二.丢番图方程

(1).形态： $a_1x_1^{b_1}+...+a_nx_n^{b_n}=c,a_{1...n},b_{1...n},c \in \mathbb{Z}$

(2).二元线性丢番图方程： $ax+by=c,a,b,c \in \mathbb{Z}$

1.定理：

对于a,b,c\in\mathbb{Z},\exists x,y \in \mathbb{Z},使得ax+by=c\iff\gcd(a,b)\mid c

2.求解：

a.求出一个解：扩展欧几里得

$先求解ax+by=\gcd(a,b)$ $不妨假设a>b,\gcd(a,b)=pa+qb$ $则有$

\begin{aligned} ax+by &= \gcd(a,b)\\ &= \gcd(b,a \bmod b)\\ &= pb+q(a \bmod b)\\ &= qa+(p-q*\lfloor\frac{a}{b}\rfloor)b \end{aligned}

CPP

int extended_gcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	int ret,xx=x,yy=y;
	ret=extended_gcd(b,a%b,x,y);
	x=yy,y=xx-a/b*yy;
	return ret;
}

b.所有解

若

x_0,y_0

为原方程一组解，则有

\begin{cases} x=x_0+\frac{b}{\gcd(a,b)}t\\ y=y_0-\frac{a}{\gcd(a,b)}t \end{cases}

为原方程一组解，其中t为任意整数

特殊地，我们有最大正整数解和最小正整数解的关系为：

\begin{cases} x_{max}=\frac{c-y_{min}*b}{a}\\ y_{max}=\frac{c-x_{min}*a}{b} \end{cases}

三.线性同余方程

(1).形态： $ax \equiv c \pmod b$

(2).求解：

显然有 ax \equiv c \pmod b \iff ax+by=c

CPP

int extended_gcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	int ret,tmp;
	ret=extended_gcd(b,a%b,x,y);
	tmp=x,x=y,y=tmp-a/b*y;
	return ret;
} 
bool linear_equation(int a,int b,int c,int &x,int &y){
	int d=extended_gcd(a,b,x,y);
	if(c%d) return 0;
	int k=c/d;
	x*=k,y*=k;
	return 1;
}

四.第一类指数同余方程

(1).形式： $a^x\equiv b\pmod p$

(2).求解

令

x=kt-m

，其中

t=\lfloor\sqrt p\rfloor

，

0\le m\le t

，

1\le k\le\lfloor\frac{p}{t}\rfloor

则有：

a^{kt-m}\equiv b\pmod p

即

a^{kt}b^{-1}\equiv a^m\pmod p

预处理出

a^0\bmod p,a^1\bmod p,\dots,a^t\bmod p

枚举

k

，计算看有没有匹配上的数。

时间复杂度：

O(\sqrt p)

五.第二类指数同余方程

(1).形式： $x^k\equiv b\pmod p$

(2).求解：

设

a

是

p

的一个原根，先求出

b\equiv a^m\pmod p

假定

x\equiv a^y

则

a^{ky}\equiv a^m\pmod p

则

a^{ky-m}\equiv 1\pmod p

即

ky-m\equiv 0\pmod {p-1}

六.逆元

若

a \times x \equiv 1 \pmod b

，则

x

为

a

在

\bmod b

意义下的倒数，记作

a^{-1}

。

显然有

\frac{a}{b} \pmod b=a\times b^{-1} \pmod b

扩展欧几里得：前提： $p$ 不一定是质数， $a$ 为正整数， $a \perp p$ 同解线性同余方程

CPP

int extended_gcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	int ret,xx=x,yy=y;
	ret=extended_gcd(b,a%b,x,y);
	x=yy,y=xx-a/b*yy;
	return ret;
} 
bool exgcd(int a,int b,int &x,int &y){
	int d=extended_gcd(a,b,x,y);
	if(1%d) return 0;
	int k=1/d;
	x*=k,y*=k;
	return 1;
}

快速幂：

前提： $p$ 为质数， $a$ 为正整数， $a \perp p$

根据费马小定理：若 $p$ 为质数， $a \perp p$ ，则 $a^{p-1} \equiv 1 \pmod p$

则有

\begin{aligned} ax &\equiv 1 \pmod p\\ ax &\equiv a^{p-1} \pmod p\\ x &\equiv a^{p-2} \pmod p \end{aligned}

线性算法：前提： $p$ 为质数， $i$ 为正整数

显然有 $1^{-1} \pmod p$

不妨设 $k$ 为 $p/i$ 的商，r为 $p/i$ 的余数

$\therefore k*i+r=p$

$\therefore k*i+r \equiv 0 \pmod p$

同乘 $i^{-1}r^{-1}$ 可得：

$\therefore k*i^{-1}+i^{-1}\equiv 0 \pmod p$

$\therefore i^{-1} \equiv -k*r^{-1} \pmod p$

$\therefore i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor * (p \bmod i)^{-1} \pmod p$

CPP

inv[1]=1;
for(int i=2;i<p;i++)
  inv[i]=(p-p/i)*inv[p%i]%p;

七.原根

模

mod

的原根：

g

是原根当且仅当

g^0,g^1,\dots,g^{p-2}

模

mod

两两不同。

若模

mod

意义下原根存在：

$mod=1,2,4,p^{\alpha},2p^{\alpha}$ ，其中 $p$ 是奇素数， $\alpha\in\mathbb{N}_+$
原根恰好有 $\varphi(mod-1)$ 个
最小的原根一般不大，可以直接枚举
$g$ 是原根当且仅当 $\forall d\mid(mod-1),d\ne mod-1\iff g^d\ne 1$

八.二次剩余

勒让德符号：

\left(\dfrac{a}{p}\right)=\begin{cases}0&p\mid a\\1&\exists x^2\equiv a\pmod p\\-1&otherwise\end{cases}

欧拉准则：

\left(\dfrac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p

二次互反律：对于奇素数

p,q

，有

\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}

求解

x

前提：

p

为奇素数。

随机一个

a

，使得

a^2-n

为非二次剩余，令

w=\sqrt{a^2-n}

则

x=(a+w)^{\frac{p+1}{2}}

CPP

LL w,n,p; 
struct num{
	LL x,y;
	num operator *(const num b){
		num tmp;
		tmp.x=((x*b.x%p+y*b.y%p*w%p)%p+p)%p;
		tmp.y=((x*b.y%p+y*b.x%p)%p+p)%p;
		return tmp;
	}
};
LL qpow(num x,LL y,LL Mod=mod) {
	if(y==0) return 1;
	num res=x; y--;
	for(;y;y>>=1,x=x*x)
		if(y&1) res=res*x;
	return res.x%Mod;
}
LL cipolla(LL n,LL p){
	n%=p;
	if(qpow(n,(p-1)/2,p)==p-1) return -1;
	LL a;
	while(1){
		a=(rnd_64()>>1ll)%p;
		w=(((a*a)%p-n)%p+p)%p;
		if(qpow(w,(p-1)/2,p)==p-1) break;
	}
	
	num x={a,1};
	return qpow(x,(p+1)/2,p);
}
void solve(){
	cin>>n>>p;
	if(!n){
		cout<<"0\n";
		return ;
	}
	LL ans1=cipolla(n,p),ans2=p-ans1;
	if(ans1==-1) cout<<"Hola!\n";
	else {
		if(ans1==ans2) cout<<ans1<<"\n";
		else cout<<min(ans1,ans2)<<" "<<max(ans1,ans2)<<"\n";
	}
	return ;
}

九.中国剩余定理

(1).内容：

若自然数

m_{1...r}

两两互质，记

M=m_1m_2...m_r

则方程：

\begin{cases} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_2}\\ ...\\ x \equiv a_r \pmod {m_r} \end{cases}

在\bmod M意义下有唯一解

。

(2).过程：

计算 $n_i=\frac{M}{m_i}$
计算 $n_i$ 在 $\bmod m_i$ 意义下的逆元 ${n_i}^{-1}$
计算 $c_i=n_i*{n_i}^{-1}$ (不对 $m_i$ 取模)
则方程在 $\bmod M$ 意义下的唯一解为： $x=\sum_{i=1}^{r}a_ic_i \pmod M$

CPP

int extended_gcd(__int128 a,__int128 b,__int128 &x,__int128 &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	__int128 ret,tmp;
	ret=extended_gcd(b,a%b,x,y);
	tmp=x,x=y,y=tmp-a/b*y;
	return ret;
}
signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>r;
	for1(i,1,r) cin>>m[i]>>a[i],M*=m[i];
	for1(i,1,r){
		n[i]=M/m[i];
		extended_gcd(n[i],m[i],x,y);
		c[i]=n[i]*x;
		madd(ans,a[i]*c[i],M);
	}
	cout<<ans;
    return 0;
}

(3).扩展中国剩余定理：

若模数不两两互质。

先考虑

x \equiv a_1 \pmod {m_1},x \equiv a_2 \pmod {m_2}

。

转化成不定方程

x=m_1p+q_1=m_2q+a_2

即

m_1p-m_2q=a_2-a_1

。

若

\gcd(m_1,m_2)\nmid(a_2-a_1)

则无解。

否则可以转化成

x\equiv m_1p+a_1\pmod {lcm(m_1,m_2)}

CPP

__int128 extended_gcd(__int128 a,__int128 b,__int128 &x,__int128 &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	__int128 ret,tmp;
	ret=extended_gcd(b,a%b,x,y);
	tmp=x,x=y,y=tmp-a/b*y;
	return ret;
}
bool linear_equation(__int128 a,__int128 b,__int128 c,__int128 &x,__int128 &y){
	__int128 d=extended_gcd(a,b,x,y);
	if(c%d) return 0;
	__int128 k=c/d;
	x*=k,y*=k;
	return 1;
}
void solve(){
	cin>>r;
	for1(i,1,r) {
		rin(m); rin(a);
		linear_equation(M,-m,a-A,p,q);
		A=M*p+A,M=lcm(M,m);
		madd(A,M,M);
	}
	rout(A);
	return ;
}

(4).大部翻倍法

CPP

void merge(LL &a1,LL &m1,LL a2,LL m2){
	if(m1<m2) swap(m1,m2),swap(a1,a2);
	while(a1%m2!=a2) a1+=m1;
	m1=lcm(m1,m2);
}
void solve(){
	cin>>n;
	v=0,d=1;
	for1(i,1,n){
		cin>>a>>m;
		a%=m;
		merge(v,d,a,m);
	}
	cout<<v<<"\n";
}

十.积性函数

(1).定义

积性函数：对于函数

f(x)

，若

\forall a,b\in\mathbb{N}^+,\gcd(a,b)=1,f(ab)=f(a)f(b)

，则称

f(x)

为积性函数。

完全积性函数：对于函数

f(x)

，若

\forall a,b\in\mathbb{N}^+,f(ab)=f(a)f(b)

，则称

f(x)

为完全积性函数。

常见的积性函数： $\varphi,\mu,\sigma,d$
常见的完全积性函数： $\varepsilon,I,id$

其中：

\varepsilon(n)=\left[n=1\right],I(n)=1,id(n)=n

积性函数的性质：

设 $n=\prod p_i^{\alpha_i}$ $n = \prod p_{i}^{α_{i}}$ ，那么 $f(n)=\prod f(p_i^{\alpha_i})$ $f (n) = \prod f (p_{i}^{α_{i}})$
- 于是可以用线性筛求出 $g(n)=p_1^{\alpha_1}$ ，然后 $f(n)=f(g(n))f(\frac{n}{g(n)})$ ，在 $O(n)$ 时间内预处理积性函数的值。
若 $f(n)$ ， $g(n)$ 都是积性函数，那么 $fg$ ， $f/g$ 都是积性函数。

(2).欧拉函数 $\varphi$

1.定义

若

n=\prod_{i=1}^{s}{p_i}^{k_i}

，其中

p_i

为质数，则

\varphi(n)=n\prod_{i=1}^{s}\frac{p_i-1}{p_i}

，表示小于等于

n

和

n

互质的数的个数$

2.性质：

$若n为质数，\varphi(n)=n-1$
$若n为奇数，\varphi(n)=\varphi(2n)$
$若a \perp b,\varphi(ab)=\varphi(a)\varphi(b)$
$n=\sum_{d \mid n}\varphi(d)$
$若n=p^k,且p为质数，\varphi(n)=p^k-p^{k-1}$

3.求法

a.单个：

CPP

int euler_phi(int n){
	int ans=n,sq=sqrt(n);
	for1(i,2,sq)
		if(n%i==0){
			ans=ans/i*(i-1);
			while(n%i==0) n/=i;
		}
	if(n>1) ans=ans/n*(n-1);
	return ans;
}

b.多个：

$筛法：$

$设p_1为n的最小质因子，n'=\frac{n}{p_1}，显然有\varphi(p_1)=p_1-1$

$若n'\bmod p_1=0,\varphi(n)=p_1*\varphi(n')$

$若n'\bmod p_1\ne0,\varphi(n)=\varphi(p_1)*\varphi(n')$

CPP

void euler_phi(int n){
	phi[1]=1;
	for1(i,2,n){
		if(!vis[i]) pri.p_b(i),phi[i]=i-1;
		for(int j: pri){
			if(i>n/j) break;
			vis[i*j]=1;
			if(i%j==0){
				phi[i*j]=phi[i]*j;
				break;
			}
			phi[i*j]=phi[i]*phi[j];
		}
	}
}

(3).莫比乌斯函数 $\mu$

1.定义

\mu(n)= \begin{cases} 1&n=1\\ 0&n的质因子最高次数>1\\ (-1)^k&n的质因子最高次数=1 \end{cases}

其中

k

为

n

的质因子个数。

2.性质

\begin{cases} 1&n=1\\ 0&n\ne1 \end{cases}

即

\sum\limits_{d\mid n}\mu(d)=\varepsilon(n),\mu\ast1=\varepsilon

3.求法

线性筛：

CPP

void get_mu(int n){
	mu[1]=1;
	for1(i,2,n){
		if(!vis[i]) pri.p_b(i),mu[i]=-1;
		for(int j: pri){
			if(i>n/j) break;
			vis[i*j]=1;
			if(i%j==0){
				mu[i*j]=0;
				break;
			}
			mu[i*j]=-mu[i];
		}
	}
}

(4).约数之和 $\sigma$ 与约数个数 $d$

1.定义

若

n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times\dots p_n^{\alpha_n}

则：

d(n)=(1+\alpha_1)\times(1+\alpha_2)\times\dots\times(1+\alpha_n)

\sigma(n)=(1+p_1^1+p_1^2+\dots+p_1^{\alpha_1})\times(1+p_2^1+p_2^2+\dots+p_2^{\alpha_1})\times\dots\times(1+p_n^1+p_n^2+\dots+p_n^{\alpha_1})

=\prod\limits_{i=1}^n(\sum_{j=0}^{\alpha_i}p_i^j)

=\prod\limits_{i=1}^n\frac{1-p_i^{\alpha_i+1}}{1-p_i}

2.求法

线性筛求 $d$ $t_i$ 表示 $i$ 的最小质因子的次数，即 $\min(\alpha_1,\dots,\alpha_n)$ 。

CPP

void make_d(){
    t[1]=d[1]=1;
    for1(i,2,n){
		if(!vis[i]) pri.p_b(i),t[i]=1,d[i]=2;
		for(int j: pri){
			if(i>n/j) break;
			vis[i*j]=1;
			if(i%j==0){
				t[i*j]=t[i]+1;
				d[i*j]=d[i]*(t[i*j]+1)/(t[i]+1);
				break;
			}
			t[i*j]=1;
			d[i*j]=d[i]*d[j];
		}
    }
}

线性筛求 $\sigma$ $t_i=\min(\sum_{j=0}^{\alpha_1}p_1^j,\dots,\sum_{j=0}^{\alpha_n}p_n^j)$ 。

CPP

void make_sgm(){
    sigma[1]=1;
    for1(i,2,n){
		if(!vis[i]) pri.p_b(i),t[i]=i+1,sigma[i]=i+1;
		for(int j: pri){
			if(i>n/j) break;
			vis[i*j]=1;
			if(i%j==0){
				t[i*j]=t[i]*j+1;
                sigma[i*j]=sigma[i]*t[i*j]/t[i];
				break;
			}
			t[i*j]=j+1;
			sigma[i*j]=sigma[i]*sigma[j];
		}
    }
}

十一.欧拉定理

(1).内容：

若

\gcd(a,m)=1

，则

a^{\varphi(m)} \equiv 1\pmod m

(2).扩展：

a^b\equiv \begin{cases} a^{b\bmod\varphi(m)},& \gcd(a,m)=1\\ a^b,& \gcd(a,m)\ne 1,b<\varphi(m)\\ a^{(b\bmod\varphi(m))+\varphi(m)}&\gcd(a,m)\ne 1,b\ge\varphi(m) \end{cases} \pmod m

十二.威尔逊定理

对于素数

p

有

(p-1)!\equiv-1\pmod p

十三.数论分块

一般用来求形如

\sum_{i=1}^nf(i)g(\lfloor\frac{n}{i}\rfloor)

若可以

O(1)

计算

f(r)-f(l)

时。

我们考虑将

\lfloor\frac{n}{i}\rfloor

相同的数放一起计算以使复杂度降至

O(\sqrt n)

UVA11526 H(n)

CPP

LL H(LL n){
	LL ans=0;
	for(LL i=1,j;i<=n;i=j+1){
		j=n/(n/i);
		ans+=(j-i+1)*(n/i);
	}
	return ans;
}

文章操作

一.斐蜀定理

(1).内容：

(2).推广

1.逆定理

2.扩展

(3).进一步结论

二.丢番图方程

(1).形态：a1x1b1+...+anxnbn=c,a1...n,b1...n,c∈Za_1x_1^{b_1}+...+a_nx_n^{b_n}=c,a_{1...n},b_{1...n},c \in \mathbb{Z}a1​x1b1​​+...+an​xnbn​​=c,a1...n​,b1...n​,c∈Z

(2).二元线性丢番图方程：ax+by=c,a,b,c∈Zax+by=c,a,b,c \in \mathbb{Z}ax+by=c,a,b,c∈Z

1.定理：

2.求解：

a.求出一个解：扩展欧几里得

b.所有解

三.线性同余方程

(1).形态：ax≡c(modb)ax \equiv c \pmod bax≡c(modb)

(2).求解：

四.第一类指数同余方程

(1).形式：ax≡b(modp)a^x\equiv b\pmod pax≡b(modp)

(2).求解

五.第二类指数同余方程

(1).形式：xk≡b(modp)x^k\equiv b\pmod pxk≡b(modp)

(2).求解：

六.逆元

七.原根

八.二次剩余

九.中国剩余定理

(1).内容：

(2).过程：

(3).扩展中国剩余定理：

(4).大部翻倍法

十.积性函数

(1).定义

(2).欧拉函数 φ\varphiφ

1.定义

2.性质：

3.求法

a.单个：

b.多个：

(3).莫比乌斯函数 μ\muμ

1.定义

2.性质

3.求法

(4).约数之和 σ\sigmaσ 与 约数个数 ddd

1.定义

2.求法

十一.欧拉定理

(1).内容：

(2).扩展：

十二.威尔逊定理

十三.数论分块

相关推荐

评论

(1).形态： $a_1x_1^{b_1}+...+a_nx_n^{b_n}=c,a_{1...n},b_{1...n},c \in \mathbb{Z}$

(2).二元线性丢番图方程： $ax+by=c,a,b,c \in \mathbb{Z}$

(1).形态： $ax \equiv c \pmod b$

(1).形式： $a^x\equiv b\pmod p$

(1).形式： $x^k\equiv b\pmod p$

(2).欧拉函数 $\varphi$

(3).莫比乌斯函数 $\mu$

(4).约数之和 $\sigma$ 与约数个数 $d$