gcd有关结论

设d=gcd(a,b)

1. $d是用s*a+tb能够表示的最小正整数$

2. $若c是a,b的公约数,则c|d$

3. $若c|d,则c|a且c|b$

4. $gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1$

5. $gcd(fib(a),fib(b))=fib(gcd(a,b))$

6. $gcd(a,b)=gcd(a-b,b),差分数组gcd与原数组gcd相同$

7. $gcd(a,b)=gcd(a,a+b)=gcd(a,k{\times}a+b)$

8. $lcm(a,b)=a{\times}b/gcd(a,b)$

9. $gcd(k{\times}a,k{\times}b)=k{\times}gcd(a,b)$

10. $gcd(a,b,c)=gcd(gcd(a,b),c)$

11. $若gcd(a,b)=d,则gcd(a/d,b/d)=1,即a/d,与b/d互素$

12. $设p为质数,gcd(p^x,p^y)=p^{min(x,y)},lcm(p^x,p^y)=p^{max(x,y)}$

13. $lcm(a,b,c)=(a{\times}b{\times}c{\times}gcd(a,b,c))/(gcd(a,b)gcd(a,c){\times}gcd(b,c))$

14. $lcm(S)=\prod_{T\subseteq{S}}{gcd(T)^{-1(|T|+1)}}$

15. 数组任意子集的gcd最大值和最小值(子集大小大于等于2)，均为从数组中任取两数的gcd的最大值和最小值