整数的整除性
这两天学离散数学，看网上的视频，从数论开始讲的，里面涉及到了一些感觉对ACM数论有帮助的式子，记下来：
已知a，b的唯一质因数分解：
GCD分解：
素因子相乘取小数
这个的意思用例子说明吧：
12=2^2 * 3^1 * 5^0 ;
15=2^0 * 3^1 * 5^1;
则GCD(12,15)= 2^0 * 3^1 * 5^0 =3;
感觉挺有用的
/*----------------------------------------------------------------------------------------------*/
LCM分解：
素因子相乘取大数
例：
12=2^2 * 3^1 * 5^0 ;
15=2^0 * 3^1 * 5^1;
LCM(12,15)=2^2 * 3^1 * 5^1=60;
/*----------------------------------------------------------------------------------------------*/
GCD（a，b）*LCM（a，b）=a*b；
未知a，b的唯一质因数分解：
欧几里得算法(Euclidean Algorithm) 与 贝祖等式(Bezout's Equation)
欧几里得算法（辗转相除法）：
定理：
GCD(int a,int b)
{
if(b==0)
return a;
else
return GCD(b,a%b);
} 贝祖等式
对于不全为0的整数a，b，d，方程sa+td=d存在整数解s和t当且仅当GCD（a，b）|d；
回代发：sa+tb=GCD（a，b）存在整数解，设s0，t0；
若d=k*GCD（a，b），则k*s0，k*t0是方程的一个解。
若方程sa+tb=d存在整数解s和t，则GCD（a，b）|（sa+td）=d
腾讯音乐娱乐集团一面123人在聊
