学习笔记【数学相关】

数学相关

质数：

质数是指在大于 \(1\) 的自然数中，除了 \(1\) 和它本身以外不再有其他因数的自然数。
\(N\) 以内的质数大约有 \(\frac{N}{\ln N}\)个

约数：

约数，又称因数。整数 \(a\) 除以整数 \(b\) (\(b≠0\)) 除得的商正好是整数而没有余数，我们就说 \(a\) 能被 \(b\) 整除，或 \(b\) 能整除 \(a\) 表示为 \(b\mid a\)。

例题1：分解质因数

唯一分解定理：

正整数 \(N\) 可被唯一分解为：

\[N=p_1 ^{c_1}\,p_2 ^{c_2} ... \,p_{n-1} ^{c_{n-1}}\,p_{n} ^{c_{n}}，其中 c_i \in \mathbb{N^+},p_i \mid N \]

引理：

正整数 \(N\) 最多有一个大于 \(\sqrt{N}\) 的质因子。

solution：

枚举质因数 \(i\) 不断试除，最后若大于 \(1\) ，则代表有大于 \(\sqrt{n}\) 的质因子，且该质因子的次数为 \(1\) 。时间复杂度为 \(O(\log_2N-\sqrt{N})\)

代码

#include
#include
#include
using namespace std;
const int P=1e6+5;
int pr[P];
int main(){
    int T; scanf("%d",&T);
    while(T--){
        int a; scanf("%d",&a);
        memset(pr,0,sizeof(pr));
        int num=0;
        for(int i=2;i<=a/i;i++){
            int cnt=0;
            if(a%i==0){
                while(a%i==0)
                    a/=i,cnt++;
                printf("%d %d\n",i,cnt);
            }
        }
        if(a>1) printf("%d %d\n",a,1); 
        puts("");
    }
    return 0;
}

例题2：试除法求约数

引理：

一个正整数 \(N\) 不是完全平方数，那么它的约数是成对出现的，设 \(a\mid N,b\mid N\) ，且 \(ab=N,a ，则有\(a<\sqrt{n}\,\,\,\,,\,\,\,\,\,b>\sqrt{n}\)

solution:

模拟即可，特判完全平方数。

代码

#include
#include
using namespace std;
const int Q=6e6+5;
int yue[Q];
inline void sum(int a){
	int cnt=0,sqr=sqrt(a);
	for(int i=1;i<=sqr;i++)
		if(a%i==0) 
			yue[++cnt]=i;
	int zong;
	if(sqr*sqr==a) zong=cnt*2-1;
	else		   zong=cnt*2;
	for(int i=1;i<=cnt;i++){
		printf("%d ",yue[i]);
		yue[zong-i+1]=a/yue[i];
	}
	for(int i=cnt+1;i<=zong;i++)
		printf("%d ",yue[i]);
	puts("");
}
int main(){
	int n;scanf("%d",&n);
	for(int i=1,a;i<=n;i++){ 
		scanf("%d",&a);
		sum(a);
	}
	return 0;
}

欧拉筛：

可以做到线性 \(O(n)\) 筛出 \(1-n\) 的质数，原理在于确保了合数 \(i\) 一定是被它最小的质因子筛掉。

代码

#include
using namespace std;
const int Q=6e6+5,N=1e8+5;
int n,q;
int pr[Q];
bool check[N];
inline void xxs(){
	int cnt=0;
	for(int i=2; i<=n; i++) {
		if(!check[i]) pr[++cnt]=i;
		for(int j=1; j<=cnt; j++) {
			if(i*pr[j]>n) break;
			check[i*pr[j]]=1;
			if(i%pr[j]==0) break;
		}
	}
}
int main() {
	xxs();
	scanf("%d%d",&n,&q);
	for(int i=1,k; i<=q; i++) {
		scanf("%d",&k);
		printf("%d\n",pr[k]);
	}
	return 0;
}

例题3：约数个数，约数之和

给定 \(n\) 个正整数 \(a_i\) ，请你输出这些数的乘积的约数个数与和，答案对 \(10^9+7\) 取模。

引理1：

正整数 \(N\) 的正约数个数为：

\[\prod _{i=1} ^{n} (c_i+1) \]

证明：

首先对 \(N\) 分解质因数：\(N=p_1 ^{c_1}\,p_2 ^{c_2} ... \,p_{n-1} ^{c_{n-1}}\,p_{n} ^{c_{n}}\)。\(p_1 ^{c_1}\) 的约数有 \(p_1 ^{0},p_1 ^{1},p_1 ^{2}...p_1 ^{c_1}\) 共 \((c_1+1)\) 个，同理 \(p_2 ^{c_2}\) 的约数有 \((c_2+1)\) 个，\(p_i ^{c_i}\) 的约数就有 \((c_i+1)\) 个，根据乘法原理， \(N\) 的约数个数就为 \((c_1+1)\times (c_2+1)\times (c_3+1)\times ... \times (c_n+1)\) 即 \(\prod _{i=1} ^{n} (c_i+1)\) 个。

证毕。

引理2：

正整数 \(N\) 的正约数之和为：

\[\prod _{i=1} ^n(\sum ^{c_i} _{j=0}p_i ^j\,) \]

证明：

首先对 \(N\) 分解质因数：\(N=p_1 ^{c_1}\,p_2 ^{c_2} ... \,p_{n-1} ^{c_{n-1}}\,p_{n} ^{c_{n}}\)。\(p_1 ^{c_1}\) 的约数有 \(p_1 ^{0},p_1 ^{1},p_1 ^{2}...p_1 ^{c_1}\)，同理，\(p_i ^{c_i}\) 的约数有 \(p_i ^{0},p_i ^{1},p_i ^{2}...p_i ^{c_i}\)。实际上 \(N\) 的约数是从 \(p_1 ^{c_1},p_2 ^{c_2} ... ,p_{n-1} ^{c_{n-1}},p_{n} ^{c_{n}}\)的约数中分别挑一个相乘得来，可知共有 \(\prod _{i=1} ^{n} (c_i+1)\) 种挑法。由乘法原理可得。

证毕。

solution：

我们需要保存一个质因数的次数，而数太大正常的数组存不下，所以开一个 \(\text{map}\) 来存。

map用法

代码

#include
#include
#define mo 1000000007 
using namespace std;
typedef long long LL;
int main()
{
	int n;
	scanf("%d",&n);
	map pr;
	while(n--){
		int a;scanf("%d",&a);
		for(int i=2;i<=a/i;i++)
			while(a%i==0) a/=i,pr[i]++;
		if(a>1) pr[a]++;
	}
	
	//求约数个数
	LL ans=1;
	map::iterator iter;
	for(iter=pr.begin();iter!=pr.end();iter++)
		ans=ans*(iter->second+1)%mo;
	//
	
	
	//求约数之和
	LL ans=1;
	map::iterator iter;
	for(iter=pr.begin();iter!=pr.end();iter++){
		int p=iter->first,a=iter->second;
		LL t=1;
		while(a--)
			t=(t*p+1)%mo;//手模一下
		ans=ans*t%mo;
	}
	//
	printf("%lld",ans);
	return 0;
}

例题4：

例题5：

例题6：

例题7：

欧拉函数：

对正整数 \(n\) ，欧拉函数是小于 \(n\) 的正整数中与 \(n\) 互质的数的个数，记作 \(\varphi(n)\) 。

引理1：

\[\varphi(n)=n\times \prod_{p\mid n且p为质数} (1-\frac{1}{p}) \]

朴素求法代码

#include
using namespace std;
int phi(int x){
	int ans=x;
	for(int i=2;i<=x/i;i++){
		if(x%i==0){
			ans=ans/i*(i-1);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) ans=ans/x*(x-1);
	return ans;
}

时间复杂度 \(O(\sqrt n)\) 。

性质1：

若 \(p\mid n\) 且 \(p^2\mid n\) ，\(\varphi(n)=\varphi(\frac{n}{p})\times p\)。

性质2：

若 \(p\mid n\) 且 \(p^2\not\mid n\) ，\(\varphi(n)=\varphi(\frac{n}{p})\times (p-1)\)。
这样就有了筛法求欧拉函数：

筛法代码

inline void xxs(){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!phi[i]) pr[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt;j++){
            if(i*pr[j]>n) break;
            if(i%pr[j]==0){//性质1
            	phi[i*pr[j]]=phi[i]*pr[j];
            	break;
			} 
            else phi[i*pr[j]]=phi[i]*(pr[j]-1);//性质2
        }
    }
}

例题1：

例题2：

快速幂：

快速算底数的 \(n\) 次幂。其时间复杂度为 \(O(log_2N)\)。原理为：

代码

#include
using namespace std;
typedef long long LL;
int a,b,mod;
inline LL qpow(LL a,LL b){
    LL res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
} 
int main(){ 
    scanf("%d%d%d",&a,&b,&mod);
    printf("%lld",qpow(a,b));
    return 0;
}

例题1：

同余：

给定一个正整数 \(m\) ，如果两个整数 \(a\) 和 \(b\) 满足 \(m\mid a-b\) ，即(a-b)/m得到一个整数，那么就称整数 \(a\) 与 \(b\) 对模 \(m\) 同余，记作 \(a\equiv b(\bmod m)\)。

性质：

反身性： \(a≡a (\bmod m)\) ；
对称性：若 \(a≡b(\bmod m)\) ，则 \(b≡a (\bmod m)\) ；
传递性：若 \(a≡b(\bmod m)\) ， \(b≡c(\bmod m)\) ，则 \(a≡c(\bmod m)\) ；
同余式相加：若 \(a≡b(\bmod m)\) ， \(c≡d(\bmod m)\) ，则 \(a+c≡b+d(\bmod m)\) ；
同余式相乘：若 \(a≡b(\bmod m)\) ， \(c≡d(\bmod m)\) ，则 \(ac≡bd(\bmod m)\) 。

费马小定理：

若 \(p\in \mathbb{P}\) ，且 \(p\not\mid a\) ，则有：

\[a^{p-1}\equiv 1(\bmod p) \]

欧拉定理：

设 \(m,a\in \mathbb{N^+}\) ，且 \(\gcd(a,m)=1\) ，则有：

\[a^{\varphi(m)}\equiv 1(\bmod m) \]

欧拉定理推论：

设 \(m,a\in \mathbb{N^+}\) ，且 \(\gcd(a,n)=1\) ，对于 \(\forall b\in \mathbb{N^+}\) ，有：

\[a^b\equiv a^{b\bmod \varphi(m)}(\bmod m) \]

例题1：同余方程

求关于 \(x\) 的同余方程 \(ax ≡ 1 (\bmod b)\)的最小正整数解。

扩展欧几里得算法：

用来求 \(ax+by=\gcd(a,b)\) 的整数解。

代码

LL x,y;
inline void exgcd(LL a,LL b){
    if(!b){
        x=1,y=0;
        return ;
    }
    exgcd(b,a%b);
    LL nx=x;
    x=y,y=nx-a/b*y;
}

solution：

对于此题，我们要求的就是 \(ax+by=1\) ，但是我们只会求 \(ax+by=\gcd(a,b)\) ，能保证 \(a,b\) 互质吗？答案是能的：

引理1：

方程 \(ax+by=m\) 的必要条件是： \(m \bmod \gcd(a,b)=0\) 。

此题保证有解，所以 \(\gcd(a,b)=1\) 。

通解：

方程 \(ax+by=\gcd(a,b)\) 中若有常数 \(k_1,k_2\) ,将 \(x+k_1,y-k_2\)带入仍能使方程成立,那么 \((x+k_1),(y-k_2)\) 就是一组新解。

\[a(x+k_1)+b(y-k_2)=\gcd(a,b) \]

\[ax+by+ak_1-bk_2=\gcd(a,b) \]

\[ak_1=bk_2 \]

为得到所有的解，需满足 \(ak_1=bk_2=t\times \text{lcm}(a,b)(t\in \mathbb(N))\)，\(\therefore k_1=\frac{b}{\gcd(a,b)},k_2=\frac{a}{\gcd(a,b)}\) 。

推广:

求 \(ax+by=c\) 的整数解。

设 \(d=\gcd(a,b)\) 。
在原式两边同乘 \(\frac{c}{d}\) 。

\[ax\frac{c}{d}+by\frac{c}{d}=c \]

那么 \(x'=x\times \frac{c}{d},y'=y\times \frac{c}{d}\) 就是一组新的解。
若 \(d\not\mid c\) 无解。

例题2：

乘法逆元：

如果整数 \(a,n\) 互质，使 \(ax \equiv 1\pmod n\) 成立的 \(x\)，称为 \(a\) 关于 \(n\) 的乘法逆元，记为 \(a^{-1}\)。

求法：

在 \(n\in\mathbb{P}\) 时可用费马小定理 \(x=a^{n-2}\bmod n\) 。
在 \(\gcd(a,n)=1\) 时可用扩展欧几里得定理， \(x\) 即为所求。
线性推逆元公式：\(inv[i]=(p?p/i)×inv[p\bmod i]\bmod p\) 。

显然扩展欧几里得应用更加广泛。

中国剩余定理：

设 \(m_1,m_2,m_3 \cdots,m_n\) 是两两互质的整数，\(M=\prod\limits_{i=1}^{n}m_i,M_i=M/m_i\) ，\(inv_i\) 是 \(M_i\) 在模 \(m_i\) 意义下的逆元。对于 \(\forall a_1,a_2,a_3,\cdots ,a_n,a_i\in \mathbb{N}\)，方程组
\(\begin{cases}x\equiv a_1 (\bmod m_1)\\x\equiv a_2 (\bmod m_2)\\x\equiv a_3(\bmod m_3)\\\cdots \\x\equiv a_n(\bmod m_n) \end{cases}\)，有整数解 \(x=(\sum\limits^{n}_{i=1} a_iM_iinv_i)\bmod M\) 。

代码

#include
using namespace std;
typedef long long LL;
const int N=15;
int n; 
LL M=1,Mi[N],inv[N];
LL m[N],a[N];
LL x,y;
inline void exgcd(LL p,LL q){
    if(!q){
        x=1,y=0;
        return ;
    }
    exgcd(q,p%q);
    LL tx=x;
    x=y,y=tx-p/q*y;
}
inline void CRT(){
    LL ans=0;
    for(int i=1;i<=n;i++){
        Mi[i]=M/m[i];
        exgcd(Mi[i],m[i]);
        inv[i]=(x%m[i]+m[i])%m[i];
        ans=(ans+(a[i]*Mi[i]%M*inv[i])%M)%M;
    }
    printf("%lld",ans);
}
int main(){
    scanf("%d",&n); 
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&m[i],&a[i]);
        M*=m[i];
    }
    CRT();
    return 0;
}

例题一：曹冲养猪

有若干头猪，建立了 \(a_i\) 个猪圈，有 \(b_i\) 头猪没有去处，求有多少头猪。

solution：

可列出同余方程组：

\[\begin{cases}x\equiv b_1 (\bmod a_1)\\x\equiv b_2 (\bmod a_2)\\x\equiv b_3(\bmod a_3)\\\cdots \\x\equiv b_n(\bmod a_n) \end{cases}\]

套 \(\text{CRT}\) 模板就好了。

代码

\\跟模板一样不放了。

组合数学：

组合：\(C_n^m=\frac{n!}{m!(n-m)!}\) 。

排列：\(A_n^m=\frac{n!}{(n-m)!}\) 。

性质：

互补性： \(C_n^m=C_n^{n-m}\) 。
组合恒等式：

\[C^m_n=C^{m}_{n-1}+C^{m?1}_{n-1} \]

\[\sum_{i=0}^nC_n^i=2^n \]

\[m?C_n^m=n?C_{n?1}^{m?1} \]

\[C_n^i=C_n^{i-1}\times (n-i+1)\times \frac{1}{i} \]

\[\dots \]

卢卡斯定理：

\[C_n^m\bmod p=C_{n/p}^{m/p}\times C_{n\bmod p}^{m\bmod p} \]

代码

inline int lucas(LL a,LL b,int p){
    if(a



二项式定理：
\[(a+b)^n=\sum\limits_{i=0}^nC_n^ia^ib^{n?i}
\]

代码
#include
using namespace std;
typedef long long LL;
const int N=1e6+5,p=1e9+7;
int inv[N],c[N];
int main(){
    int n,a,b; scanf("%d%d%d",&n,&a,&b);
    inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=(LL)(p-p/i)*inv[p%i]%p;
    c[0]=1;
    for(int i=1;i<=n;i++)
        c[i]=(LL)c[i-1]*(n-i+1)%p*inv[i]%p;//在同行内推杨辉三角。
    printf("%d",c[b]);
    return 0;
}


证明一下：
\(C_n^i=C_n^{i-1}\times (n-i+1)\times \frac{1}{i!}\)
我们用柿子表示出来：
\[C_n^i=\frac{n!}{i!(n-i)!}①，C_n^{i-1}=\frac{n!}{(i-1)!(n-i+1)!}②
\]
\(②\times (n-i+1)\)，阶乘约掉一个剩下 \((n-i)!\) ，分母再乘个 \(i\) ，(i-1)!变成 \(i!\) 就和所求一样了。
证毕[滑稽]。

\(\text{Catalan}\) 数列
\(\mathbf{1,1,2,5,14,42,132,429}\)。
\[f_n=C_{2n}^n-C_{2n}^{n+1}=\frac{C_{2n}^{n}}{n+1}
\]
 

 

 
矩阵乘法：
设 \(A\) 为 \(n\times k\) 矩阵，\(B\) 为 \(k\times m\) 矩阵，那么它们的乘积 \(C\) 为一个 \(n\times m\) 矩阵。
\[C_{i,j}=\sum ^k _{r=1} A_{i,r}\times B_{r,j} 
\]
矩阵乘法满足结合律，分配律但不满足交换律。

矩阵快速幂：
原理同普通的快速幂。

单位矩阵为：
\[\begin{bmatrix}
1 & 0 & \cdots & 0\\
0 & 1 & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & 1
\end{bmatrix}\]
重载运算符版本的代码。

用途：

加速递推来快速求出数列中某一项的值。
加速形如？？？的转移方程。


用途1：
例题1：P1939 矩阵加速（数列）
我们把原矩阵放在左面，想要得到的矩阵放在右面：
\(\begin{bmatrix} a_{x-1} & a_{x-2} & a_{x-3}  \end{bmatrix}
\quad\) \(\times\) \(\begin{bmatrix} ? & ? & ? \\ ? & ? & ? \\ ? & ? & ? \end{bmatrix}
\quad\) \(=\) \(\begin{bmatrix} a_{x} & a_{x-1} &a_{x-2} \end{bmatrix}
\quad\)
下面我们考虑构造这个矩阵。
\(\because a_{x}=a_{x-1}+a_{x-3}\),
\(\therefore\) 可确定第一列：

\(\begin{bmatrix} 1 & ? & ? \\ 0 & ? & ? \\ 1 & ? & ? \end{bmatrix}\)
原来的 \(a_{x-2}\) 变成了 \(a_{x-1}\) 这样就又确定一列：\(\begin{bmatrix} 1 & 1 & ? \\ 0 & 0 & ? \\ 1 & 0 & ? \end{bmatrix}\)。
同理：\(\begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}\)
这样矩阵就构造好了。
在 \(x\leq3\) 时，\(a_{x}\) 都为 \(1\) ，所以初始矩阵为\(\begin{bmatrix} 1 & 1 & 1  \end{bmatrix}
\quad\) 。
然后通过矩阵快速幂用 \(O(\log_2n)\) 的时间内求出第 \(n\) 项。

代码
#include
#include
using namespace std;
typedef long long LL;
const int mod=1e9+7;
struct Matrix{
	LL c[5][5];
}a,res;
Matrix operator * (const Matrix &x,const Matrix &y){
	Matrix t;
 	memset(t.c,0,sizeof(t.c));
 	for(int i=1;i<=3;i++)
 		for(int j=1;j<=3;j++)
 			for(int k=1;k<=3;k++)
 				t.c[i][j]=(t.c[i][j]+x.c[i][k]*y.c[k][j]%mod)%mod;
 	return t;
}
inline void qpow(int k){
	res.c[1][1]=1,res.c[1][2]=1,res.c[1][3]=1;
	a.c[1][1]=1,a.c[1][2]=1,a.c[1][3]=0,
	a.c[2][1]=0,a.c[2][2]=0,a.c[2][3]=1,
	a.c[3][1]=1,a.c[3][2]=0,a.c[3][3]=0;
	while(k){
		if(k&1) res=res*a;
		a=a*a;
		k>>=1;
	} 
	printf("%lld\n",res.c[1][1]);
}
int main(){
	int T; scanf("%d",&T);
	while(T--){
		int n; scanf("%d",&n);
		if(n<=3){
			printf("1\n");
			continue;
		}
		qpow(n-3);
	}
	return 0;
}


注：一定要确定好初始矩阵的值。

例题2：P1962 斐波那契数列
依题意我们构造出矩阵：

\(\begin{bmatrix} 1 & 1 \\ 1 & 0  \end{bmatrix}
\quad\)
然后跑矩阵快速幂即可。

代码
#include
#include
using namespace std;
typedef long long LL;
const int mod=1e9+7;
struct Matrix{
	LL c[5][5];
}a,res;
Matrix operator * (const Matrix &x,const Matrix &y){
	Matrix t;
	memset(t.c,0,sizeof(t.c));
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			for(int k=1;k<=2;k++)
				t.c[i][j]=(t.c[i][j]+x.c[i][k]*y.c[k][j]%mod)%mod;
	return t;
}
inline void qpow(LL k){
	a.c[1][1]=1,a.c[1][2]=1,
	a.c[2][1]=1,a.c[2][2]=0;
	res.c[1][1]=res.c[1][2]=1;
	while(k){
		if(k%2==1) res=res*a;
		a=a*a;
		k=k>>1;
	}
	printf("%lld",res.c[1][1]);
}
int main(){
	LL n; scanf("%lld",&n);
	if(n<=2) return puts("1"),0;
	qpow(n-2);
	return 0;
}



例题3：斐波那契数列和
同样我们设一个的矩阵：

\(\begin{bmatrix} F_x & F_{x-1} & sum_{x}\end{bmatrix}
\quad\)

然后同理构造出一个矩阵：

\(\begin{bmatrix} 1 & 1 & 1\\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix}
\quad\)

做矩阵快速幂即可。

代码
#include
#include
using namespace std;
const int mod=1e9+7;
typedef long long LL;
struct M{
	int c[5][5];
}a,res;
M operator * (const M &x,const M &y){
	M t;
	memset(t.c,0,sizeof(t.c));
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
			for(int k=1;k<=3;k++)
				t.c[i][j]=((LL)t.c[i][j]+(LL)x.c[i][k]*y.c[k][j]%mod)%mod;
	return t;
}
inline void qpow(LL b){
	a.c[1][1]=1,a.c[1][2]=1,a.c[1][3]=1,
	a.c[2][1]=1,a.c[2][2]=0,a.c[2][3]=1,
	a.c[3][1]=0,a.c[3][2]=0,a.c[3][3]=1;
	res.c[1][1]=1,res.c[1][2]=1,res.c[1][3]=2;
	while(b){
		if(b%2==1) res=res*a;
		a=a*a;
		b/=2;
	}
	printf("%d\n",res.c[1][3]);
}
int main(){
	LL n; scanf("%lld",&n);
	if(n<=2){
		if(n==1) puts("1");
		else	 puts("2");
		return 0;
	}
	qpow(n-2);
	return 0;
}



用途2：
例题1：


						
							

						
							
							
			B学习笔记数学：质数数学：同余数学：欧拉函数欧拉定理数学：约数数学：欧几里得拓展欧几里得数学：快速幂数学：中国剩余定理数学：高斯消元数学：容斥原理数学：组合数学数学：矩阵乘法


					
					
					
						相关
						
				
						
			
																
								
										拓展欧几里得求逆元
									
									
								 

        
								
							
							

																
								
										数学篇 辗转相除，拓展欧几里得求逆元
									
									
								 

        
								
							
							

																
								
										【CodeForces】906 D. Power Tower 扩展欧拉定理
									
									
								 

        
								
							
							

																
								
										MongoDB学习笔记：分片
									
									
								 

        
								
							
							

																
								
										【javaweb学习笔记】WEB03_JavaScript
									
									
								 

        
								
							
							

																
								
										JavaWeb学习笔记(3)
									
									
								 

        
								
							
							

																
								
										MongoDB学习笔记-2、MongoDB简介与安装
									
									
								 

        
								
							
							

																
								
										Matlab学习笔记（2）绘图命令
									
									
								 

        
								
							
							

																
								
										Matlab学习笔记（2）绘图命令
									
									
								 

        
								
							
							

																
								
										Matlab学习笔记（2）绘图命令
									
									
								 

        
								
							
							

																
								
										Matlab学习笔记（2）绘图命令
									
									
								 

        
								
							
							

																
								
										Matlab学习笔记（2）绘图命令

学习笔记 【数学相关】

数学相关

质数：

约数：

例题1：分解质因数

唯一分解定理：

引理：

solution：

例题2：试除法求约数

引理：

solution:

欧拉筛：

例题3：约数个数，约数之和

引理1：

证明：

证毕。

引理2：

证明：

证毕。

solution：

例题4：

例题5：

例题6：

例题7：

欧拉函数：

引理1：

性质1：

性质2：

例题1：

例题2：

快速幂：

例题1：

同余：

性质：

费马小定理：

欧拉定理：

欧拉定理推论：

例题1：同余方程

扩展欧几里得算法：

solution：

引理1：

通解：

推广:

例题2：

乘法逆元：

求法：

中国剩余定理：

例题一：曹冲养猪

solution：

组合数学：

组合：\(C_n^m=\frac{n!}{m!(n-m)!}\) 。

排列：\(A_n^m=\frac{n!}{(n-m)!}\) 。

性质：

卢卡斯定理：

二项式定理：

证明一下：

证毕[滑稽]。

\(\text{Catalan}\) 数列

矩阵乘法：

矩阵快速幂：

用途：

用途1：

例题1：P1939 矩阵加速（数列）

注：一定要确定好初始矩阵的值。

例题2：P1962 斐波那契数列

例题3：斐波那契数列和

用途2：

例题1：

相关

学习笔记【数学相关】