1.欧几里得算法（辗转相除法）求最小公倍数。
递归写法：
int gcd(int a,int b)
{
if(b == 0) return a;
else
return gcd(b,a%b);
}
更简洁的写法：
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
扩展：
Lcm (最大公约数)
lcm(a,b) = (a*b)/gcd(a,b);
为了防止a*b超long long 溢出，所以建议这样写：
lcm(a,b) = a/gcd(a,b)*b;
2.引入求余概念
求余：
a%b = a mod b = a-a/b*b （一般题目中b 都是 正整数）//ex:a=5,b=3
注：当a为负整数时, 应保证取模结果为正，所以 (a%b+b)%b //类似钟表的概念
同余：
定义：给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。
a≡b(mod m) 称为 a与b对mod m 同余
可推理的结论： a % b = m，因为(a – b) mod m = 0
例如：26≡2(mod 12) ， (26-2) mod12 = 0
模运算公式：
(a + b) % p = (a%p + b%p) %p （对）
(a - b) % p = (a%p - b%p) %p （对）
(a * b) % p = (a%p * b%p) %p （对）
(a / b) % p = (a%p / b%p) %p （错） ----- 为什么是错的呢( •̀∀•́ )？
证明一个公式是对的难，但是举一个反例就行!
Ex：(100/50) = 2 ≠ (100 ) / (50 ) = 0
那么我们要怎么解决酱紫的问题呢？
这就要用到逆元了，我会在下一篇博客中详细介绍。
