最大公因数与最小公倍数
++++++++++++++++++++++

最大公因数
^^^^^^^^^^

数学中一般用 :math:`\gcd(a,b)` 表示两个整数 :math:`a` 和 :math:`b` 的最大公因数。显然，此运算满足交换律。

.. math::

    \gcd(a,b)=\gcd(b,a)

求取两个正整数的最大公因数一般采用辗转相除法，也称为欧几里德法，是古希腊数学家欧几里德发现的一种用来快速计算两个整数的最大公因数的算法。这个算法非常快速，而且非常适合计算机算法实现。辗转相除法求最大公因数的原理来源于最大公因数的两个性质：

1. 任何整数和0的最大公因数，它和它自己的最大公因数都就是这个整数自己。

.. math::

    \gcd(a,0)=\gcd(a,a)=a

2. 两个不相等的整数的最大公因数等于大数除以小数得到的余数和小整数的最大公因数。

.. math::

    a\gt b\implies \gcd(a,b)=\gcd(a \bmod b,b)

辗转相除法就是利用上面的两条性质，不断地用大数去除小数，把大数变成除得的余数，直到其中有一个数变为0，此时另一个数就是要求的最大公因数。举例说明如下。

.. admonition:: 示例

   1. :math:`\gcd(16, 12) = \gcd(4, 12) = \gcd(4, 0) = 4`
   2. :math:`\gcd(14, 3) = \gcd(2, 3) = \gcd(2, 1) = \gcd(0, 1) = 1`
   3. :math:`\gcd(48, 36) = \gcd(12, 36) = \gcd(12, 0) = 12`
   4. :math:`\gcd(105, 21) = \gcd(0, 21) = 21`
   5. :math:`\gcd(7, 7) = \gcd(0, 7) = 7`


**算法实现**

用一个循环条件是两数均不为0的循环即可实现辗转相除法。

.. code-block:: c++

   int gcd(int a, int b)
   {
           while (a && b)
                   if (a > b)
                           a %= b;
                   else
                           b %= a;
           return a + b;
   }

.. note::

   1. 循环条件 ``(a && b)`` 相当于 ``(a != 0 && b != 0)``\ ，也就是当 ``a`` 或者 ``b`` 中的任何一个是0的时候，循环就结束了。
   2. 循环结束之后，``a`` 和 ``b`` 中肯定至少有一个等于0，最大公因数就是另一个数。为了简化程序，我们利用任何数加上零等于它自己的性质，直接把结果赋值为 ``a+b`` 即可，无需再去判断其中哪一个是0了。

利用c++ 的三元运算，可以把上面这个函数的代码进一步简化。

.. code-block:: c++

   int gcd(int a, int b)
   {
           while (a && b && (a > b ? a %= b : b %= a));
           return a + b;
   }

利用多个整数最大公因数的数学性质 :math:`\gcd(a, b, c)=\gcd(\gcd(a,b),c)` 可以方便地循环调用上面的 ``gcd()`` 函数求出任意个正整数的最大公因数。

.. attention::

    以上算法仅对0和正整数有效，尽管对于绝大部分算法程序已经足够，但也可能出现需要处理负数的情况，请自行设法修改以适应负数。


最小公倍数
^^^^^^^^^^

有了求最大公因数的方法之后，求最小公倍数 :math:`\text{lcm}(a,b)` 的方法便呼之欲出了。根据整数论的知识，我们知道两个整数的最大公因数和最小公倍数之积等于两个整数之积。

.. math::

   \text{lcm}(a,b)\cdot\gcd(a,b)=a\cdot b


写成C++程序，唯一要注意的是两个整数相乘的积可能会整数超限，所以用先除后乘的方法处理即可，代码如下。

.. code-block:: c++

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

和最大公因数的情况一样，多个数的最小公倍数也可以拆分成两两链式求解：:math:`\text{lcm}(a,b,c)=\text{lcm}(\text{lcm}(a,b),c)`\ 。也可以先求出所有数的最大公因数，然后利用数学规律“\ :math:`n` 个数的最小公倍数等于它们的乘积除以它们的最大公因数的 :math:`n-1` 次方”来求解。

.. math::

   \text{lcm}(a_1,a_2,\dots,a_n)=\frac{a_1\cdot a_2\cdot\cdots\cdot a_n}{[\gcd(a_1,a_2,\dots,a_n)]^{n-1}}

第二种方法的编程实现技巧性比较强，并不是简单的相乘相除就可以的。

.. admonition:: 练习

   编写一个程序，输入 :math:`n` 正整数并求出它们的最大公因数和最小公倍数，其中 :math:`2\le m\lt 10`。

   输入共两行，第一行一个整数 :math:`n`\ ，第二行 :math:`n` 个正整数 :math:`a_1,\dots,a_n`\ ，均小于100，相互之间用一个空格隔开。

   输出一行，为两个正整数，先后为 :math:`\gcd(a_1,\dots,a_n)` 和 :math:`\text{lcm}(a_1,\dots,a_n)`\ ，中间用一个空格隔开。


互质判断
^^^^^^^^

有了快速的最大公因数算法之后，判断两个整数是否互质成为一个极其简单的问题，只需判断它们的最大公因数是否为1即可。在通常情况下，这样的算法都是很简单很快速的，也可以用来在一系列整数中搜索互质数对。

然而如果是要在一个很大的范围内搜索互质数对或者计算互质数对的数量，例如将一百万个正整数两两配对一共有5×10\ :superscript:`11`\ （五千亿）个数对，要在这中间统计所有互质数对，用循环穷举并计算最大公因数的方法是行不通的。遇到这类问题就要用到更加复杂和精心设计的算法了，这个问题留到后面的章节再讨论。

最后要说一下两个以上整数\ :strong:`相互互质`\ 的概念，这是指所有数相互之间\ :strong:`两两互质`\ 。检查多个整数是否相互互质需要对它们进行两两配对逐对检查，一旦发现一对不互质的数检查就可以结束了。许多人想当然地以为所有数的最大公因数为1就代表它们是相互互质的，其实这是错误的。例如 :math:`\gcd(4,5,6)=1`\ ，但是它们并不是。

下面是用来判断一个整数数组中的数是否互质的一个简单的函数。

.. code-block:: c++

   template <int N>
   bool is_coprime(int (&a)[N])
   {
           for (int i = 0; i < N - 1; i++)
                   for (int j = i + 1; j < N; j++)
                           if (gcd(a[i], a[j]) != 1)
                                   return false;
           return true;
   }