第十二单元 数论算法12.1 同余的性质12.2 最大公约数、最小公倍数

第十二单元 数论算法

12.1 同余的性质!

注意下面三个式子，它可以保证在计算中不会发生溢出。
 (a＋b) mod m＝(a mod m＋b mod m) mod m
 (a－b) mod m＝(a mod m－b mod m＋m) mod m

 (ab) mod m＝(a mod m)×(b mod m) mod m

12.2 最大公约数、最小公倍数!

求最大公约数只需用欧几里得算法（辗转相除法）。
求最小公倍数需要用到最大公约数与最小公倍数的关系：

 可以看到，程序先做除法后做乘法，这样可防止计算过程中发生溢出。

int gcd(int a, int b) { return (b==0) ? a : gcd(b, a%b); }
int lcm(int a, int b) { return a / gcd(a,b) * b; }

 让 gcd 运算次数最多的一对数是斐波那契数。即使这样，gcd 也不会爆栈。
gcd 可以改写成非递归算法：

int gcd(int a, int b)
{
int t=a%b;
while(t)
{
a=b;
b=t;
t=a%b;
}
return b;
}