【数学】整除

开数论坑了TAT

本文介绍整除、最小公倍数、最大公约数和扩展欧几里得算法等基础知识。

退役边缘人，近期整理下模板啦~

基本概念与性质

• 偶数、奇数
• $\mod: a=qb+r,0\leq r<|b|\neq 0$，记作$r=a\mod b$
• $a|b,a|c\Rightarrow \forall x,y,a|bx+cy$ ，$a$ 称公因子，最大的记作$\gcd(a,b)$（对应有最小公倍数$lcm(a,b)$）。
• $a|b,b|c\Rightarrow a|c$
• $m\neq 0,a|b\Leftrightarrow ma|mb$
• $a|b,b|a\Rightarrow a=\pm b$
• $a|b,b\neq 0\Rightarrow |a|\leq |b|$
• $a|m,b|m\Rightarrow lcm(a,b)|m;d|a,d|b\Rightarrow d|\gcd(a,b)$
• $ab=\gcd(a,b)\times \text{lcm}(a,b)$
• $m,a,b\in N^+,\text{lcm}(ma,mb)=m\times \gcd(a,b)$

辗转相除法（欧几里得算法）

$a=qb+r,0\leq r<|b|\neq 0,\gcd(a,b)=\gcd(b,r)$

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

扩展欧几里得：

$\gcd(a,b)=xa+yb$ ，求解$x,y$ 。

推论：$\gcd(a,b)=1\Leftrightarrow a,b互素\Leftrightarrow 存在xa+by=1$

算法计算次数：拉梅定理（咕咕咕）

// 扩展欧几里得：ax+by=gcd(a,b)=d
void exgcd(ll a, ll b, ll &d, ll &x, ll &y)
{
    if (!b)
    {
        x = 1, y = 0, d = a;
        return;
    }
    exgcd(b, a % b, d, y, x);
    y -= a / b * x;
}