python/TangDou/AcWing/NumberTheory/最大公约数的性质.md

最大公约数的性质

性质1

gcd(a,a)=a //一个数与自己的最大公约数是本身

性质2

gcd(ka,kb)=k*gcd(a,b) //分配律

性质3

gcd(a, b, c) = gcd(gcd(a, b), c) //结合律

性质4

若gcd(k,b)=1，则gcd(ka,b)=gcd(a,b)

性质5

gcd(a,b) = gcd(b,a-b) //辗转相除法 gcd(a_1,a_2,a_3,...a_n)=gcd(a_1,a_2-a_1,a_3-a_2,...,a_n-a_{n-1})

性质6

gcd(a,b) = gcd(a, a+b) = gcd(a,ka+b)

性质7

若gcd(a, b) = d，则gcd(a/d, b/d) = 1，即a/d与b/d互素。这个定理很重要。

常见题套路

gcd满足区间可加性，区间的gcd问题常常使用线段树维护

习题：https://codeforces.com/contest/1459/problem/C https://blog.csdn.net/qq_53629286/article/details/122692425 https://blog.csdn.net/weixin_44316314/article/details/105892187 这里面有一些我未学习过的性质，等功力到了再来看