整除与最大公约数

公式挂掉太丑了就看这里

数论1：整除与最大公约数

素因子个数

![img](file:///C:\Users\cting\Documents\Tencent Files\2397161038\Image\C2C\Image1\BB0C943C9D4993CBF866D2F1E952DB7D.jpg)

带余除法与整除

整除符号：a | b （a是b的约数）

算术基本的定理：

质因数分解唯一

结论（复杂度计算相关）：

素数无限

$\pi(n)$ ：小于等于n的素数个数
$$
\lim_{n\rightarrow\infty}\frac{\pi(n)\ln n}n=1\
P_n=O(n\log n)\
\sum_{i=1}^n \frac1i=O(\log n)\
\sum_{1\leq p\leq n} \frac 1p=O(\log\log n)\
$$

整除性质：

a | c, b | c, (a, b) = 1 , 则 ab | c
a | bc , (a, b) = 1, 则 a | c （因为ab互质，所以a因子一定在c里）
p | ab, 则 p|a 或 p | b

公约数

gcd: ()， lcm: []

结论：**[a,b] * (a, b) = a * b**

证明：
$$
a=p_1^{a_1}p_2^{a_2}…p_k^{a_k}, ,,,b=p_1^{b_1}p_2^{b_2}…p_k^{b_k}, ,,,
d=p_1^{d_1}p_2^{d_2}…p_k^{d_k}\
则(a,b)=\prod p_i^{min(a_i,b_i)},,,,[a,b]=\prod p_i^{max(a_i,b_i)},,,,
\therefore (a,b)[a,b]=a\times b
$$

欧几里得算法：

(a, b) = (a - b, b) = (b, a mod b)

(a, b) -> (b, a mod b) -> ….

O (log (min(a, b)))

对于多个数做欧几里得算法的复杂度：n + log (max{ai})

lcm(a, b) = (a / (a, b)) * b //防爆ll

gcd求法二: a,b中偶数的 /= 2，适用大整数

裴蜀定理

一定存在整数解，满足 ax + by = gcd (a, b)

(a, b) | d $\leftrightarrow$ au + bv = d，存在整数解 u, v

裴蜀的严谨证明见扩欧

扩展欧几里得

系数化为欧几里得，分解a
$$
ax+by=1\rightarrow b(\lfloor \frac ab \rfloor +a \mathrm{,,mod,,} b)x+by=1\
\rightarrow b(\lfloor \frac ab\rfloor x+y)+(a\mathrm{,,mod,,} b)x=1,
令x’=\lfloor \frac ab\rfloor x+y,y’=x,
\则x=y’,y=x’-\lfloor \frac ab\rfloor y’,转化为bx’+(a\mathrm{,,mod,,} b)y’=1
$$

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

扩欧通解计算

特解：$x_1, y_1$

通解（左减右加）：
$$
x=x_1+\frac{b}{(a, b)} t, ,,,y=y_1-\frac a{(a, b)}t, t是任意系数
$$

习题

（大致按照难度升序）

裴蜀

【模板】裴蜀定理：https://www.luogu.com.cn/problem/P4549

裴蜀简单推广到多个变量，最小的就是所有数求个gcd

买不到的数目：https://www.luogu.com.cn/problem/P3951

一个不是很严谨的想法：a,b都要拿的时候，最小不能凑成的数目是 a * b，因为要么拿a个b，要么拿b个a，而ab都要拿且互质，所以不可能凑成a * b的大小。a,b可以都不拿，答案就是 a*b - a - b。严谨证明见扩欧

麦香牛块Beef McNuggets：https://www.luogu.com.cn/problem/P2737

Fox And Jumping： https://codeforces.com/problemset/problem/510/D

https://www.luogu.com.cn/problem/P4571

https://www.luogu.com.cn/problem/P2520

扩展欧几里得

两道模板：

http://oj.daimayuan.top/course/12/problem/487

用exgcd求出最小解之后利用通解的公式在限定范围内调节

其实只需调节一次，因为exgcd解出的就是最小解

http://oj.daimayuan.top/course/12/problem/488
$$
ax+by=m,同除d’=gcd(a,b)(此时不能整除就无解),\
化为a’x+b’y=d’,则必有x_1=x_0d’,y_1=y_0d’这一组解\
有通解x=x_1+b’t,y=y_1-a’t,且最小解x满足0<x<b’\
按照此逻辑调整即可，要注意也要满足x_1,y_1\geq0
$$

Sakana~

数论1：整除与最大公约数

数论1：整除与最大公约数

带余除法与整除

算术基本的定理：

结论（复杂度计算相关）：

整除性质：

公约数

欧几里得算法：

裴蜀定理

扩展欧几里得

扩欧通解计算

习题

裴蜀

扩展欧几里得

相关题单