GCD LCM 题解

· · 个人记录

问题描述

给你数n, m，求无序数对(a,b)，使得gcd(a, b) = n \bigvee lcm(a, b) = m的个数.

唯一分解定理

任何一个大于1的整数n都可以分解成若干个质因数的连乘积，如果不计各个质因数的顺序，那么这种分解是惟一的.

我们按照质数从小到大的顺序，得到的对应幂的排列表示为n = 2^{k_1} \times 3^{k_2} \times 5^{k_3} \times ... = <k_1, k_2, k_3, ..., k_p>

证明：

  1. 如果n为质数，那么显然可以分解成一个唯一分解排列<0, ..., n>.

  2. 如果n不为质数，那么显然可以分解为至少两个大于1的整数.

    如果分解出的是质数，适用情况1. 如果分解出的不为质数，继续分解，直到全为质数或1为止.

所以根据数学归纳法，我们得到任何一个大于1的整数n都可以分解成若干个质因数的连乘积.

若a, b均可被分解成一个唯一分解排列.，则有：

a =\space <a_1, a_2, a_3, ..., a_i, ..., a_k> \\ b =\space <b_1, b_2, b_3, ..., b_i, ..., b_k> \\ a \times b = (2^{a_1} \times 2^{b_1}) \times (3^{a_2} \times 3^{b_2}) \times ... =\space<a_1 + b_1, a_2 + b_2, .., a_k + b_k>

以上推导出若a, b均可被分解成一个唯一分解排列.，那么a\times b也可被分解成一个唯一分解排列，且每一位都是a, b对应位之和.

同理可得，若a, b均可被分解成一个唯一分解排列.，那么a/b也可被分解成一个唯一分解排列，且每一位都是a, b对应位之差（必须为非负数）.

那么我们就有：任何一个大于1的整数n都可以分解成一个唯一分解排列.

唯一分解定理在最大公约数/最小公倍数问题的应用

若a, b可被分解成两个唯一分解排列，那么它们的最大公约数也可被分解成唯一分解排列，且其每一位是a, b对应位的最小值.

若a, b可被分解成两个唯一分解排列，那么它们的最小公倍数也可被分解成唯一分解排列，且其每一位是a, b对应位的最大值.

证明：

  1. 若想满足$(a\space|\space k)$，那么$k$的唯一分解排列中每一位数不能大于$a$的唯一分解排列对应的数. 若想满足$(b\space|\space k)$，那么$k$的唯一分解排列中每一位数不能大于$b$的唯一分解排列对应的数. 那么若想满足$(a\space|\space k \bigwedge b\space |\space k)$，那么$k$的唯一分解排列中每一位数不能大于$a, b$的唯一分解排列对应的数. $k$取最大值，则$k$的唯一分解排列中每一位数都为$a, b$唯一分解排列中每一位数的最小值.
  2. 若想满足$(k\space|\space a)$，那么$k$的唯一分解排列中每一位数不能小于$a$的唯一分解排列对应的数. 若想满足$(k\space|\space b)$，那么$k$的唯一分解排列中每一位数不能小于$b$的唯一分解排列对应的数. 那么若想满足$(k\space|\space a \bigwedge k\space |\space b)$，那么$k$的唯一分解排列中每一位数不能小于$a, b$的唯一分解排列对应的数. $k$取最小值，则$k$的唯一分解排列中每一位数都为$a, b$唯一分解排列中每一位数的最大值.

解法

\begin{array}{l} \operatorname{let}\space a =\space <a_1, a_2, a_3, ..., a_i, ..., a_k> \\ \operatorname{let}\space b =\space <b_1, b_2, b_3, ..., b_i, ..., b_k> \\ \operatorname{then}\space gcd(a, b) =\space <min(n_1, m_1), min(n_2, m_2), ..., min(n_k, m_k)>\space=\space<n_1, n_2, n_3, ..., n_i, ..., n_k> \\ \operatorname{then}\space lcm(a, b) =\space <max(n_1, m_1), max(n_2, m_2), ..., max(n_k, m_k)>\space=\space <m_1, m_2, m_3, ..., m_i, ..., m_k> \\ \end{array}

若想满足题设，那么\forall i \in [1, k], 都满足 \space(a_i = n_i \bigwedge b_i = m_i) \bigvee (a_i = m_i \bigwedge b_i = n_i) 才能使得min(a_i, b_i) = min(n_i, m_i) = n_i \bigwedge max(a_i, b_i) = max(n_i, m_i) = m_i.

所以对于唯一分解排中的每一位数，都有两种选择（除非n_i = m_i），选择总数为2^{t - 1}. （无序数对，要除2）

（以上t是n_i \ne m_i的个数.）

上述过程假定\forall i \in [1, k], n_i < m_i. 实际上是不一定的，此种情况无解.