『数学笔记』提高组部分

LPR_318 · 2025-07-24 19:35:25 · 算法·理论

一些闲话

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

正文部分

因数

因数（Divisor），也称为约数，是指整数 a 除以整数 b（b \not= 0）所得的商为整数且没有余数，此时称 b 为 a 的因数，a 为 b 的倍数。\ 若某一个数 p 是 a 的因数，且 p 为质数，则称 p 为 a 的质因数。

唯一分解定理：

每一个大于 1 的自然数都可以唯一分解为质数的乘积，且这种分解不考虑质数排列顺序时是唯一的。‌‌\ 也就是说，我们可以将大于 1 的自然数 N 写成以下形式：

其中，k 为质因数个数，p_i 为第 i 个质因数（一般来说从小到大），\alpha_i 为该质因数的次数。

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

实际上 N 的因数是在 p_1^{\alpha_1},......,p_k^{\alpha_k} 每一个的因数中分别挑一个相乘得来。\ 因数之和也就是各个质因数的各个次方相加后相乘。

GCD 与 LCM

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

逆元与同余

• 同余：记 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。

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}。

代码：

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;
}

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。

扩展欧拉定理：

可用于降幂，形式如下：

代码：

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)。\ 它有一堆推论或推广：

• 一定存在整数 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 为质数，则 (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!}。\ 组合数有以下性质：

多重集的排列和组合：

1. 无限多重集的排列：\
2. 有限多重集的排列：\
3. 有限多重集的组合：\

二项式系数：

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

1. 递推：C_n^r = C_{n-1}^{r-1} + C_{n-1}^{r}。
2. 逆元：C_n^r \bmod m = \

卢卡斯定理：

对于质数 m：\

错位排列：