数学知识

· · 算法·理论

gcd 与 lcm

几个重要的公式：

\gcd(a,b)=\gcd(a,a+b)=\gcd(b,a\mod b) \gcd(k\times a,k\times b)=k\times\gcd(a,b) \gcd(a,b,c)=\gcd(\gcd(a,b),c) 若\gcd(a,b)=d，则\gcd(a/d,b/d)=1，互素

算数基本定理

任何一个大于1的自然数N，如果N不是质数，那么N可以唯一分解成有限个质数的乘积：n=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}}，其中 p 为素数。

由此，设 a=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}},b=p_{1}^{f_{1}}p_{2}^{f_{2}}...p_{m}^{f_{m}}，

则 \gcd(a,b)=p_{1}^{\min(c_{1},f_{1})}p_{2}^{\min(c_{2},f_{2})}...p_{m}^{\min(c_{m},f_{m})}，

#### 所以 $lcm(a,b)=a\times b/\gcd(a,b)$。 ### 例题 给定 $L,G$，问满足 $gcd(x,y,z)=G$ 与 $lcm(x,y,z)=L$ 的 $x,y,z$ 有多少个。 注意问题变形为满足 $\gcd(x/G,y/G,z/G)=1,lcm(x/G,y/G,z/G)=L/G$ 的$(x/G),(y/G),(z/G)$ 有多少个。 由算术基本定理，令 $(x/G) = p_{1}^{i_{1}},p_{2}^{i_{2}},p_{3}^{i_{3}}$, $(y/G)=p_{1}^{j_{1}},p_{2}^{j_{2}},p_{3}^{j_{3}}$, $(z/G)=p_{1}^{k_{1}},p_{2}^{k_{2}},p_{3}^{k_{3}}$, $(L/G)=p_{1}^{t_{1}},p_{2}^{t_{2}},p_{3}^{t_{3}}$。 根据 $\gcd$ 与指数的关系，我们可以知道要使式子成立，则 $\min({i_{1},j_{1},k_{1}})=0$ 满足互素性质，接下来分类讨论取值满足 $\max({i_{1},j_{1},k_{1}})=t_{1}$，实际需要分解 $G/L$ 的质因数。 # 裴蜀定理 #### 若 a,b 为正整数，则有 x,y 使 ax+by=gcd(a,b) #### 推论：a 与 b 互素当且仅当 ax + by=1，也就是gca(a,b)=1 # 线性丢番图方程 也叫一元二次不定方程形如 $ax+by=c$，$a,b$ 为常数，$x,y$ 为变量。 #### 定理：设 d = gcd(a,b)，若d 不能整除 c，方程无解；否则方程有特解 $(x_{0},y_{0})$，通解 $x=x_{0}+(b/d)n,y=y_{0}-(a/d)n$。 如何求？ #### 扩展欧几里得算法 先用扩展欧几里得求出 $ax+by=\gcd(a,b)$ 的特解 $(x_{0},y_{0})$，令此式左右同乘 $(c/gcd(a,b))$ 变为 $ax_{0}c/gcd(a,b)+by_{0}c/gcd(a,b)=c$，所以 $ax+by=c$ 的特解就是 $x^{'}=x_{0}c\gcd(a,b),y^{'}=y_{0}c\gcd(a,b)$。 ```cpp int exgcd(int a,int b,int &x,int &y){ if(!b){ x=1,y=0; return a; } d = exgcd(b,a%b,y,x); y -= a/b * x; return d; } ``` # 同余 ## 一元线性同余方程 ## 逆元 对于非零整数 $a,m$，如果存在 $b$ 使得 $ab\equiv 1\pmod m$，就称 $𝑏$ 是 $a$ 在模 $m$ 意义下的逆元。 这相当于说，$b$ 是线性同余方程 $ax\equiv 1\pmod m$ 的解。根据 线性同余方程 的性质可知，当且仅当 $\gcd(a,m)=1$，即 $a,m$ 互素时，逆元 $a^{-1}\bmod m$ 存在，且在模 $m$ 的意义下是唯一的。 求解逆元的多种形式： ### 单个逆 $exgcd$：要求 $\gcd(a,m)=1 
void ex_gcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1;
    y = 0;
  } else {
    ex_gcd(b, a % b, y, x);
    y -= a / b * x;
  }
}

快速幂：要求 m 为素数
根据费马小定理 a*a^{m-2}=a^{m-1}\equiv 1\pmod m 以及逆元的唯一性可知，逆元 a^{-1}\bmod p 就等于 a^{p-2}\bmod p，因此可以直接使用 快速幂 在 O(\log p) 时间内计算：

int qpow(int a, int b, int m) {
  long long res = 1, po = a;
  for (; b; b >>= 1) {
    if (b & 1) res = res * po % m;
    po = po * po % m;
  }
  return res;
}

int inverse(int a, int p) { return qpow(a, p - 2, p); }

多个逆

线性递推求逆：

同余方程组

𝑥 ≡𝑎1(mod𝑛1)

𝑥 ≡𝑎2(mod𝑛2)

⋮

𝑥 ≡𝑎𝑘(mod𝑛𝑘)

求同余方程组的解

中国剩余定理 CRT

此方法只适用于模数互质的情况，步骤：

  1. 计算总模数 M = 各个模数之积
  2. 计算 m_{i}=\frac{M}{n_{i}}
  4. 方程在模 M 意义下的唯一解：x=\sum_{i=1}^{n}a_{i}\times m_{i}\times m_{i}^{-1}(mod M) 
    for(int i=1;i<=n;i++){
    read(a[i]); read(b[i]);
    M = M * a[i];//模数的乘积 
}
for(int i=1;i<=n;i++){
    __int128 m = M / a[i],x,y;//模数积除以各自的模数 
    exgcd(m,a[i],x,y);//exgcd计算m的逆元 
    ans = (ans + b[i] * m * x % M) % M;//m * m^-1 * 权值 取模总模数 
}

整除分块

有这样一个问题：

以 n=10 为例 i 1 2 3 4 5 6 7 8 9 10
\lfloor\frac{n}{i}\rfloor 10 5 3 2 2 1 1 1 1 1

注意到 \lfloor\frac{n}{i}\rfloor 的值有重复连续的区间，这启示我们按 \lfloor\frac{n}{i}\rfloor 的值 分块。

接下来证明分块少于 2\sqrt n 种。
当 i <= \sqrt n 时，\lfloor\frac{n}{i}\rfloor 的值大于等于 \sqrt n，共 \sqrt n 个；当 i > \sqrt n 时，\lfloor\frac{n}{i}\rfloor < \sqrt n，也有 \sqrt n 个。

当一个区间内的值为 k 时，区间右端点为 \lfloor\frac{x}{k}\rfloor，证明略。

ll get(ll x){
    ll res = 0;
    for(ll i=1,j;i<=x;i=j+1){
        j = x / (x / i);
        res += (x/i) * (j - i + 1);
    }
    return res;
}
以 n=10 为例 i 1 2 3 4 5 6 7 8 9 10
\lfloor\frac{n}{i}\rfloor 10 5 3 2 2 1 1 1 1 1
i\times \lfloor \frac{n}{i} \rfloor 10 10 9 12 10 6 7 8 9 10

相当于每个区间是一个首项为 \lfloor\frac{x}{i}\rfloor\times i，尾项为 \lfloor\frac{x}{i}\rfloor\times\lfloor\frac{x}{k}\rfloor，长度为(r - l + 1) ，公差为 \lfloor\frac{n}{i}\rfloor 的等差数列。

ll get(ll x){
    ll res = 0;
    for(ll i=1,j;i<=x;i=j+1){
        ll k = x / i;
        j = x / k;
        res += k * (i + j) * (j - i + 1) / 2; 
    }
    return res;
}

例题

模拟赛遇到了，没做出来。 给定 a,b 两个序列，定义 c_{i} = \sum_{j=1}^{i} a_{\lfloor\frac{i}{j}\rfloor} \times b_{i\mod j}，求序列 c。

和上面的结论一样，根据整除分块，\lfloor\frac{n}{i}\rfloor 相同的 a 是连续的一段，且只有 sqrt_{n} 级别，注意到 i \mod j 在这相同的一段中是公差为 \lfloor\frac{n}{i}\rfloor 的等差数列的形式，所以说我们就可以利用根号分治的思想，小于根号 k 的暴力计算，大于根号 k 的进行下标的等差数列前缀和预处理，利用整除分块快速计算。

-2025.11.18