第一节：整数分解与筛法(gcd,exgcd,埃氏筛，欧拉筛，质因数分解)

整除概念：b|a
对于整数a,b,如果存在整数q使得a = bq,则a是b的倍数，b是a的因子，则有b|a

最大公因数：
最大的d满足{d|a,d|b},一般(a,b)记为最大公约数，如果两个整数互质，则gcd(a,b) = 1

[a,b]记为最小公倍数

暴力求gcd

直接遍历即可，复杂度O(min{a,b})，太慢

欧几里得求gcd

前提：设a,b,c是三个不全为0的整数，满足整数q，a = bq+c,那么(a,b) = (b,c)

证明：不妨设d|a,d|b,而c = a-bq,因为d|a,d|b,q相当于是任意倍，那么d一定能被a-bq整除，所以d|a-bq,所以(a,b) = (b,c)

而由a = bq+c，有c = a%b,所以(a,b) = (b,a%b),所以gcd(a,b) = gcd(b,a%b);