一些闲话

也是学上数学了好吧。
~~要不是要听写，正常人谁整理笔记啊。~~
膜拜神犇 Hootime 和 TA 的 npy chenyuexiC2026。

正文部分

因数

因数（Divisor），也称为约数，是指整数

a

除以整数

b

（

b \not= 0

）所得的商为整数且没有余数，此时称

b

为

a

的因数，

a

为

b

的倍数。
若某一个数

p

是

a

的因数，且

p

为质数，则称

p

为

a

的质因数。

唯一分解定理：

每一个大于

1

的自然数都可以唯一分解为质数的乘积，且这种分解不考虑质数排列顺序时是唯一的。‌‌
也就是说，我们可以将大于

1

的自然数

N

写成以下形式：

N = \prod_{i=1}^{k}{p_i}^{\alpha_i}

其中，

k

为质因数个数，

p_i

为第

i

个质因数（一般来说从小到大），

\alpha_i

为该质因数的次数。

实际上，一个大于

1

的自然数的各个因数就是由它的各个质因数组合及次方而来。
由乘法原理可得，我们可以把因数个数写成以下形式：

N = \prod_{i=1}^{k}{(\alpha_i+1)}

实际上

N

的因数是在

p_1^{\alpha_1},......,p_k^{\alpha_k}

每一个的因数中分别挑一个相乘得来。
因数之和也就是各个质因数的各个次方相加后相乘。

N = \prod_{i=1}^{k}{\sum_{j=0}^{\alpha_i}p_i^j}

GCD 与 LCM

最大公约数（Greatest Common Divisor, GCD）是指两个或多个整数共有约数中最大的一个。
最小公倍数（Least Common Multiple, LCM）是指两个或多个整数共有倍数中最小的一个。
他们有如下性质：

$\gcd(a,b) = \gcd(a,a+b) = \gcd(a,ka + b) = \gcd(a+cb,b)$ 。
$\gcd(ka,kb) = k \times\gcd(a,b)$ 。
$lcm(a,b) \times \gcd(a,b) = ab$ 。

逆元与同余

同余：记 $a \bmod m = b \bmod m$ 为 $a \equiv b \pmod m$ 。
逆元：记满足 $\gcd(a,m) = 1,ax \equiv 1 \pmod m$ 的一个解 $x$ 为 $a$ 模 $m$ 的逆，记为 $a^{-1}$ 。
费马小定理：若 $a,n$ 互质，则由 $a^{n-1} \equiv 1\pmod n$ 。
则 $a^{n-2} \bmod n$ 就是 $a$ 模 $n$ 的逆。
递推式： $i^{-1} \pmod p = (p - \frac{p}{i}) \times (p \bmod i)^{-1} \mod p$ 。

CPP

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

欧拉函数与欧拉定理

定义欧拉函数

\phi(n)

为不超过

n

且与

n

互质的正整数个数，为积性函数。

积性函数：若 $\gcd(x,y) = 1$ 且 $f(xy) = f(x) \times f(y)$ ，则称 $f(n)$ 为积性函数。

欧拉函数有以下性质：

若 $p$ 为质数，则 $\phi(p) = p-1$ ，且 $\phi(p^k) = (p-1) \times p^{k-1}$ 。
$\phi(n) = n \times \prod_{i=1}^{s}{(\frac{p_i-1}{p_i})}$ ，其中 $s$ 为 $n$ 的因数数量， $p_i$ 为第 $i$ 个因数（一般来说从小到大）。

代码：

CPP

int phi(int p){
    int ans = p;
    for(int i = 2;i * i <= p;++i){
        if(p % i == 0){
            while(p % i == 0) p /= i;
            ans /= i,ans *= (i-1);
        }
    }
	if(p > 1) ans /= p,ans *= (p - 1);
    return ans;
}

CPP

void euler_sieve(){
    for(int i = 0;i <= n;++i) phi[i] = i;
    cnt = 0;
    for(int i = 2;i <= n;++i){
        if(phi[i] == i){//如果i是质数
            primes[cnt++] = i;
            phi[i] = i - 1;// 质数的欧拉函数值是自身减1
        }
        for(int j = 0;j < cnt && primes[j] * i <= n;++j){//遍历已找到的质数
            if(i % primes[j] == 0){
                // i能被primes[j]整除，说明primes[j]是i的最小质因子
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
			else phi[i * primes[j]] = phi[i] * (primes[j] - 1);
			// i不能被primes[j]整除，primes[j]是i*primes[j]的最小质因子
        }
    }
}

欧拉定理：

若

\gcd(x,y) = 1

，则

x^{\phi(y)} \equiv 1\pmod y

。
带入欧拉定理可得费马小定理。

费马小定理：若 $y$ 为质数，则 $x^{y-1} \equiv 1\pmod y$ 。

扩展欧拉定理：

可用于降幂，形式如下：

a^b \mod m \equiv \begin{cases} a^b \mod m & b < \phi(m), \\ a^{b \mod \phi(m) + \phi(m)} \mod m & b \geq \phi(m) \text{ \& } \gcd(a, m) \neq 1, \\ a^{b \mod \phi(m)} \mod m & \gcd(a, m) = 1. \end{cases}

代码：

CPP

ph = phi(m);
ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9'){
    x *= 10,x += (ch - '0');
    if(x >= ph) x = x % ph,fl = 1;
    ch = getchar();
}
if(fl == 1) x += ph;
cout << Fastpow(a,x,m) % m;

裴蜀定理

如果

a,b

均为整数，则有整数

x,y

使得

ax + by = \gcd(a,b)

。
它有一堆推论或推广：

$a,b$ 互质当且仅当存在整数 $x,y$ ，使得 $ax + by = 1$ 。
一定存在整数 $x,y$ ，满足 $ax + by = \gcd(a,b) \times n$ 。
一定存在整数 $x_1,......,x_n$ ，满足 $\sum_{i = 1}^n a_ix_i = \gcd(a_1,......,a_n)$ 。

威尔逊定理

若

p

为整数，则

p

可以整除

(p-1)! + 1

。
这个定理可以改写成以下形式：

$[(p-1)!+1] \bmod p = 0$ 。
$(p-1)! \bmod p = 1$ 。
$(p-1)! = pq - 1$ ，且 $q$ 为正整数。
$(p-1)! \equiv -1 \pmod p$ ，这也是 $p$ 为质数的充要条件。

推论：

若 $p$ 为质数，则 $(p-1)!+1 \equiv 0 \pmod p$ 。
若 $p$ 为大于 $4$ 的合数，则 $(p-1)! \equiv 0 \pmod p$ 。

组合与排列

排列：

P_n^r=\frac{n!}{(n-r)!}

。
组合：

C_n^r=\frac{n!}{(n-r)!r!}

。
组合数有以下性质：

$C_n^r=C_n^{n-r}$ 。
$C_n^r=C_{n-1}^{r-1} + C_{n-1}^{r}$ （帕斯卡公式）。
$\sum_{i=0}^n C_n^i = 2^n$ 。

多重集的排列和组合：

无限多重集的排列：
$S$ 是一个多重集，它有 $k$ 个不同的元素，每个元素都有无穷重复个数， $S$ 的 $r$ 排列个数为 $k^r$ 。
有限多重集的排列：
$S$ 是一个多重集，它有 $k$ 个不同的元素，每个元素的重数分别为 $n_1,n_2,…,n_k$ ， $S$ 的大小是 $n = \Sigma_{i=1}^k n_i$ ，则 $S$ 的 $n$ 排列个数为 $\frac{n!}{\prod_{i=1}^{k} (n_i!)}$ 。
有限多重集的组合：
$S$ 是一个多重集，它有 $k$ 个不同的元素，每个元素都有无穷重复个数，那么 $S$ 的 $r$ 组合为 $C_{r+k-1}^r = C_{k-1}^r$ 。

二项式系数：

二项式系数有两种计算方法：

递推： $C_n^r = C_{n-1}^{r-1} + C_{n-1}^{r}$ 。
逆元： $C_n^r \bmod m =$
$\frac{n!}{r!(n-r)!} \bmod m = (n! \bmod m) \times ((r!)^{−1} \bmod m) \times ((n − r)!)^{−1} \bmod m) \bmod m$ 。

卢卡斯定理：

对于质数

m

：

C_n^r \bmod m \equiv C_{n \mod m}^{r \mod m} \times C_{\frac{n}{m}}^{\frac{r}{m}}

。

代码实现如下：

CPP

void init(){
    for(int i = 1;i <= 19491001;++i) f[i] = (f[i-1] * i) % MOD;
    for(int i = 2;i <= 19491001;++i) r[i] = (MOD - MOD / i) * r[MOD % i] % MOD;
}
int C(int n,int k){//组合数 C(n, k)
    if(k < 0 || k > n) return 0;
    if(k == 0 || k == n) return 1;
    if(k > n - k) k = n - k;
    int q1 = f[n],q2 = (f[k] * f[n-k]) % MOD;
    return q1 * r[q2] % MOD;
}
int lucas(int n,int k){//Lucas 定理计算 C(n, k) mod MOD
	//C(n,m) % p = C(n/p,m/p) * C(n%p,m%p) % p 
    if(k < 0 || k > n) return 0;
    if(k == 0) return 1;
    int res = 1;
    while(n || k){
        int ni = n % MOD,ki = k % MOD;
        if(ki > ni) return 0;
        res = (res * C(ni, ki)) % MOD;
        n /= MOD,k /= MOD;
    }
    return res;
}

容斥原理

集合的并等于集合的交的交错和（奇正偶负）。
集合的交等于全集的交减去补集的并。

Catalan 数

通项公式：

$H_n = C_{2n}^n - C_{2n}^{n-1}$ 。
$H_n = \frac{1}{n+1}C_{2n}^n$ 。
$H_n = \frac{4n+2}{n+1}H_{n-1}$ 。
注意： $2$ 和 $3$ 都有大数除法， $n$ 非常大，需要进行取模操作，直接做除法会损失精度，需要转换为逆元再取模。

圆排列：

是排列的一种，指

m

个数中选

n

个不同的元素排列成一个环形，无头无尾。两个循环排列相同当且仅当所取元素的个数相同并且元素取法一致，在环上的排列顺序一致，记作

Q_n^m

。

Q_n^n = \frac{A_n^n}{n}

。

Q_n^m = C_n^m Q_m^m = \frac{n!}{m(n-m)!}

错位排列：

n

个有序的元素应有

n!

个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排。

D_1 = 0,D_2 = 2

。

D_n = (n-1)(D_{n-1} + D_{n-2})

。

不定方程与同余方程

二元线性丢番图方程(不定方程）：

二元线性丢番图方程形如

ax + by = c

。

ax + by = c

有解的充分必要条件是

d = \gcd(a,b)

能整除

c

。
如果

(x_0,y_0)

是方程的一个特解，通解：

x = x_0 + \frac{bn}{d}

，

y = y_0 - \frac{an}{d}

。
其中

n

是任意整数。
求解一元线性同余方程等价于求解二元线性丢番图方程：

ax \equiv b \pmod m

表示

ax - b

是

m

的倍数，设为

-y

倍，则有

ax + my = b

。
这就是二元线性丢番图方程。

扩展欧几里得算法：

是欧几里得算法的扩展，用于求解两个整数

a,b

的最大公约数，同时找到满足裴蜀等式

ax + by = \gcd(a, b)

的整数解

x

和

y

。
具体过程如下：

递归过程‌：若 $b \not= 0$ ，递归计算 $gcd(b,a \bmod b)$ ，并利用当前层的商 $q = \frac{a}{b}$ 更新 $x$ 和 $y$ 的值。
下一层的解 $x_1$ 和 $y_1$ 满足 $bx_1 + (a \bmod b)\times y_1 = \gcd(b,a \bmod b)$ 。
递归终止条件‌：当 $b = 0$ 时，此时 $x = 1,y = 0$ 。
当前层的解 $x = y_1,y = x_1 - q * y_1$ 。

‌ 代码实现如下：

CPP

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

同余方程组-中国剩余定理

\begin{cases} x \equiv r_1 \pmod {m_1}, \\ x \equiv r_2 \pmod {m_2}, \\ ...... \\ x \equiv r_n \pmod {m_n}. \end{cases}

其中对于任意满足

1 \le i,j \le n

且

i \not= j

的

i,j

，保证

\gcd(m_i,m_j) = 1

。

计算所有模数的积 $M$ 。
$M = \prod_{i=1}^{n}m_i$ 。
计算第 $i$ 个方程的 $c_i$ 。
$c_i = \frac{M}{m_i}$ 。
计算 ${c_i}^{-1} \pmod {m_i}$ 。
$x = \sum_{i=1}^nr_ic_ic_i^{-1} \pmod M$ 。

CPP

int dickduck(int x,int y,int Mod){//龟速乘防止爆 long long
	int ans = 0;
	while(y >= 1){
		if(y & 1) ans = (ans + x) % Mod;
		y = y >> 1,x = (x << 1) % Mod;
	}
	return ans;
}
int exgcd(int a,int b,int &x,int &y){//扩展欧几里得算法
    if(b == 0){
        x = 1,y = 0;
        return a;
    }
    int gcd1 = exgcd(b,a % b,y,x); //递归计算并交换 x,y
    y -= a / b * x;
    return gcd1;
}
int modinv(int a,int m){//模逆元（不能保证 m 是质数，不能用快速幂） 
    int x,y;
    int gcd1 = exgcd(a,m,x,y);
    if(gcd1 != 1) return -1;//无逆元
    return (x % m + m) % m;
}
int cr(int n){//中国剩余定理
    int M = 1,x = 0;
    for(int i = 1;i <= n;++i) M *= mm[i];         //1.计算总模数 M
    for(int i = 1;i <= n;++i){
        int Mi = M / mm[i];                       // Mi(其它模数之积)
        int ti = modinv(Mi,mm[i]);                // ti(Mi 在 mod mm[i] 下的逆元)
        if (ti < 0) return -1;                    // 逆元不存在
        x = (x + dickduck(aa[i],dickduck(Mi,ti,M),M)) % M;             // 累加
    }
    return (x + M) % M;
}

同余方程组-扩展中国剩余定理

\begin{cases} x \equiv r_1 \pmod {m_1}, \\ x \equiv r_2 \pmod {m_2}, \\ ...... \\ x \equiv r_n \pmod {m_n}. \end{cases}

其中对于任意满足

1 \le i,j \le n

且

i \not= j

的

i,j

，不保证

\gcd(m_i,m_j) = 1

。
对于模数不互质的情况，我们可以通过合并相邻两组方程的方式来逐步得到解。

x \equiv r_i \pmod {m_i},x \equiv r_j \pmod {m_j}

。
转化得：

r_i - y_im_i = x,r_j - y_jm_j = x

。
所以：

r_i - y_im_i = r_j - y_jm_j