### 最大公约数的性质

#### 性质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 这里面有一些我未学习过的性质，等功力到了再来看