算法中的数学：gcd与lcm

1.最大公约数和最小公倍数

前置知识补充：

a / b = c

a：被除数

b：除数

c：商

若商无余数，则a又叫b的倍数，b又叫a的约数且可以表示为 b | a

1.1定义

最大公约数（gcd）：是一组整数中最大的共同约数

最小公倍数（lcm）：是一组整数中最小的共同倍数

所处头文件：numeric

1.2应用

求两个数的gcd和lcm时，需要用到短除法

短处法的过程就是将你看出来了的公约数提取到左侧，然后将两个数除这个公约数进入下一行，循环进行，直到公约数为1停止。

此时，gcd就是所有公约数的乘积，lcm是所有剩余的数和所有公约数的乘积

且gcd和lcm的乘积就是两个数的乘积

于是我们就得到了常用方法求最小公倍数：先求最大公约数，再根据两个数的乘积除以最大公约数得到最小公倍数

1.3欧几里得算法（辗转相除法）

最大公约数的求法就是辗转相除法

下面我们讲解一下辗转相除法的用法：

假设a>b

若b是a的约数，那么最大公约数就是b

若b不是a的约数，那么gcd(a,b)->gcd(b,a%b),然后递归进行,直到b变为0，此时a就是最大公约数

假设a < b ,gcd会先从gcd(a,b)变为gcd（b，a），然后重复上面的逻辑

代码实现：

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

每次轮转就将b放到参数1位置，将参数二变为a%b,直到b等于0，说明最大公约数出来了，返回最大公约数a

1.4例题讲解

本题需要我们用数据量极大的数据a和整型数据b求最大公约数。

但是我们的gcd求最大公约数的算法中需要求a%b，如果直接求会越界、

解决方案

第一步：存储a的时候用string存储

第二步：利用秦九韶算法处处取模来求出不越界的余数

补充：秦九韶算法

作用：将一元n次多项式的问题转化为n个一次式的的算法，大大减少了计算难度

其实本质上就是不断提取公因式，最终简化为n个一次式.

而在本题中，一个极大的十进制数，可以看成x=10的n次多项式相加。

eg：12345

看成：1 * 10^4 + 2 * 10^3 + 3 * 10^2 + 4 * 10 + 5

体现在代码上的理解就是：每次先乘10，然后加下一项，最后取余，循环进行

解题：

#include<iostream>
using namespace std;
typedef long long ll;
string a;
ll b;
ll gcd(ll a, ll b)
{return b==0 ? a : gcd(b,a%b);
}
ll cal()
{ll num = 0;for(auto e : a){num = num*10 + e -'0';num %= b;}return num;
}
int main()
{cin >> a >> b;cout << gcd(b,cal()) << endl;return 0;
}

1.这里我们一开始就把b放在前面是因为gcd算法要求第一个参数是较大的，而b一定大于等于cal计算出来的a关于b的余数。

2.其实秦九韶算法就是除法的基本原理，我们这里相当于在模拟高精度除法取余的过程。