整除

定义

若\(a=bk\) \((a, b, k \in Z)\) 则\(b\)整除\(a\)记做\(b \mid a\)

也称\(b\)为\(a\)的约数（因数） 或 \(a\)为\(b\)的倍数

性质

若 \(b\mid a\) , \(c\mid a\), \(b\perp c\) 则 \(bc\mid a\)

若 \(a \mid b\), \(b\mid a\), 则: \(\mid a \mid = \mid b \mid\)

若 \(a\mid b\), \(c \in Z\)， 则: \(a\mid bc\)

若 \(a\mid b\), \(m\in Z\) , 且 \(m \not= 0\), 则 : \(ma \mid mb\)

若 \(a\mid b\), \(a\mid c\) ,则对于任意 \(x,y\in Z\),均有 \(a\mid xb+yc\)

若 \(a\mid b\), \(a\mid c\) ,则 \(a\mid (b + c)\) , \(a \mid (b - c)\)

其实整除的题有很多，如果想好好学一学应该去找MO选手

例题 CF 762A

注意到约数总是成对出现：

若 \(k\) 是 \(n\) 的约数, 则 \((n/k)\) 也是 \(n\) 的约数。

在一对约数中，必有一个不大于

\(\sqrt n\)，另一个不小于 \(\sqrt n\)。

因此枚举 \(1.. \sqrt n\) 就能求出 \(n\) 的所有约数。