You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
|
|
|
### 最大公约数的性质
|
|
|
|
|
|
|
|
|
|
|
|
#### 性质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 这里面有一些我未学习过的性质，等功力到了再来看
|
