这两天学离散数学，看网上的视频，从数论开始讲的，里面涉及到了一些感觉对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