辗转相除法和同余原理

辗转相除法

  辗转相除法就是用来求出两个数的最大公约数的方法，那么这个方法怎么用呢？举个例子：有两个数，a=12,b=8，要求这两个数的最大公约数，首先让a%b得到4，然后让a=b,b=a%b,即现在a=8,b=4；继续用a%b得到0，然后让a=b,b=a%b，现在a=4,b=0。当b等于0的时候，a的值就是原来两个数的最大公约数
  代码如下

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

证明辗转相除法就是证明以下关系
$$gcd(a,b)=gcd(b,a\mathrm{mod}b)a$$
假设$$a\mathrm{mod}b=r$$
则需要证明$$gcd(a,b)=gcd(b,r)$$
因为$$a\mathrm{mod}b=r$$成立，所以下面连等式必定成立
$$\begin{array}{r}a=b\ast q+r\end{array}$$
$$\begin{array}{r}r=a-b\ast q\end{array}$$
其中q为自然整数
假设u是a和b的公共因子，则有：
$$\begin{array}{r}a=s\ast u\\ b=t\ast u\end{array}$$
将a和b带入到式子(1)当中得到
$$\begin{array}{rl}r& =s\ast u-t\ast u\ast q\\ & =(s-t\ast q)\ast u\end{array}$$
  这说明，u如果是a和b的公因子，那么u也是r的公因子,假设v是b和r的公因子，同理可得v也是a的公因子。
  综上，a和b的每个公因子，也是b和r的公因子，反之亦然。所以a和b的全体公因子集合 = b和r的全体公因子集合
即$$gcd(a,b)=gcd(b,a\mathrm{mod}b)a$$
证毕
  在求出a和b最大公约数r之后，最小公倍数就是
$$a\ast b/r$$
  转换成代码就是

int lcm(int a, int b)
{
   
    return a * b / gcd(a, b);
}

  在了解到以上前置知识后，来做一道题目

神奇的数字
  就用示例2为例，两个数分别是2和3，要求第4个神奇的数字，其实我们可以给出一个范围，使得第4个神奇的数字是在这个范围里面的，因为是第4个神奇的数字，那么这个数字最大不会超过2*4也就是8，范围就可以确定为【0，8】,因为即使没有3，求得可以被2整除的第4个数字最大也就是8了，由于又加了一个数字，那么在范围【0，8】内神奇数字的数目肯定是变多了的，那么第4个神奇数字必定是在【0，8】之间
  在确定了范围之后，我们可以定义一个函数f(x),该函数的返回值就是从0到x包含有多少个神奇数字。还是以2和3为例

  可以看到，在【0，8】范围内6既是2的倍数也是3的倍数，所以不管是对于2来说还是对于3来说，6都是神奇数字，即6被算作了两次神奇数字，那么我们只要进行去重，得到的神奇数字个数就是函数f(x)的返回值
  在确定了范围还有f(x)后，我们就可以使用二分法解决这道问题
代码如下：

long long gcd(int a, int b) //求最大公约数
    {
   
        return b == 0 ? a : gcd(b, a % b);
    }
    long long lcm(int a, int b) //求最小公倍数
    {
   
        return a * b / gcd(a, b);
    }
    //检查x右边有多少个数是可以被a或者b整除
    long long check(long long x, int a, int b) {
   
        return x / a + x / b - x / lcm(a, b);
    }
    int nthMagicalNumber(int n, int a, int b) {
   
        long long mod = 1e9 + 7;
        long long l = 0;
        long long r = (n % mod) * min(a, b);
        while (l < r) {
   
            long long m = (l + r) / 2;
            if (check(m, a, b) >= n)
                r = m;
            else
                l = m + 1;
        }
        return l % (mod);
    }

同余原理

加法的同余原理
$$(a+b)\mathrm{mod}c=a\mathrm{mod}c+b\mathrm{mod}c$$
乘法的同余原理
$$(a\ast b)\mathrm{mod}c=(a\mathrm{mod}c)\ast (b\mathrm{mod}c)$$

  以加法的同余原理为例，当题目要求结果对c进行取模运算时，但是在得到结果的时候，也就是a+b运算过程中，加出来的结果已经超出了当前类型的最大值，就发生了溢出的现象，这个时候再对溢出后的结果进行取模已经没有意义了，所以就需要在运算之前就分别对两个数进行取模防止溢出

减法的同余原理
$$(a-b)\mathrm{mod}c=((a\mathrm{mod}c)-(b\mathrm{mod}c)+c)\mathrm{mod}c$$
  在减法的同余原理中需要对
$$(amodc)-(bmodc)$$加上c是为了防止两数相减得到一个负数的情况