GCD，LCM

定理

a、b两个数的最大公约数乘以它们最小公倍数等于a和b的乘积

axb=GCD(a,b)xLCM(a,b)

据此定理，求3与8的最小公倍数可以为：LCM(3,8)=3x8divGCD(3,8)=24

欧几里得算法

构造关系：GCD(a,b)=GCD(b, a mod b)

 int gcd(int a,int b) 
 { 
     if(b==0)
         return a; 
    return                  gcd(b,a%b); 
 }

二进制最大公约数算法

递归终止条件：GCD(m,m)=m
递归关系式：
mm为偶数，n为偶数：Gcd(m,n)=2*Gcd(m/2,n/2)
m为偶数，n为奇数：Gcd(m,n)=Gcd(m/2,n)
m为奇数，n为偶数：Gcd(m,n)=Gcd(m,n/2)
m为奇数，n为奇数：Gcd(m,n)=Gcd(n,m-n)

不定方程的整数解

方程ax+by=c有整数解的充要条件：gcd(a,b) | c

设d=gcd(a,b)

则若我们求得一组(x0,y0)满足ax0+by0=d

则可以得到原方程的一组解:((x0Xc)/d, (y0xc)/d)

扩展欧几里得算法

作用

已知a,b,求解一组x,y，使他们满足贝祖等式[^ax+by=gcd(a,b)=d](根据数论原理，解一定存在）。常用在求解模线性方程组中，也可以用来求解乘法逆元。

Int exGcd(int a,int b,int& x,int& y)
{
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    int r=exGcd(b,a%b,x,y);
    int t=x;x=y;y=t-a/b*y;
    return r;
}

勾股数

勾股数有如下几个性质：

X,Y,Z一定两两互质
X,Y一定一奇一偶
X+Z一定是一个完全平方数
(Y+Z)/2也是一个完全平方数
XxYxZ一定能被60整除

应用举例

编程求n个（n≤100）正整数Ai（Ai≤30000，1≤i≤n）的最大公约数和最小公倍数。假设解一定在长整数范围内。

先求出两个数的最大公约数（最小公倍数），再和其他数求最大公约数（最小公倍数），只需调用函数n-1次。可以利用欧几里得算法快速实现：gcd(a1,a2,…,an)=gcd(gcd(a1,a2,…,an-1),an)

阶乘问题

整数n的阶乘n！是从1到n的所有整数的乘积。编程：输入一正整数n（n≤65000），给出n！的值从右至左有多少位连续的零？并输出n！的值从右至左第一个非零位的值。<br />
例如：n=5，则5！的值等于120，从右至左有1位连续的0；从右至左第一个非零的值为2。你的输出：<br />
1<br />
2<br />
当n=11时，程序应该输出：<br />
2<br />
8

分析：
N!的值从右至左连续零的个数，实际上等于n！中所包含的5的因子的总数，这是因为：2x5=10.而n！中包含的2的因子的总数显然比5的因子总数大得多。
在去除了所有从右至左连续的零以后，计算n！的最右非零位数值就可以用以下的公式：

(axb)%10=(a%10)x(b%10)%10

同余

定义

a%m=b%m，则称a，b mod m同余

概念

设a，b为两个整数，且它们的差a-b能被某个自然数m所整除，则就称a就模m来说同余于b，或者说a和b关于模m同余，

记为：a=b （mod m）

它意味着：a-b=mxk（k为整数）

性质

对于整数a,b,c和自然数m,n则对模m同余满足：

自反性：a = a（mod m）
对成性：若a=b（mod m），则b = a（mod m）
传递性：若a=b（mod m），b=c（mod m），则a=c（mod m）
同加性：若a=b（mod m），则a+c=b+c（mod m）
同乘性：若a=b（mod m），则aXc=bXc
一般情况，a=b（mod m），c=d（mod m），则：aXc=bXd（mod m）
同幂性：若a=b（mod m）则an(mod m)
若a mod p=x， a mod q=x，p、q互质，则a mod（pXq）=x
但是同余不满足同除性，即：a/n != b/n(mod m)

素数

素数的几个定理

唯一分解定理

若整数a>=2,那么a一定可以表示为若干个素数的乘积（唯一的形式），即a=p1xp2xp3x...ps(其中pj为素数，称为a的素因子，1<=j<=s)