题解 P1029 【最大公约数和最小公倍数问题】

sochiji

2020-02-08 00:35:07

Solution

*去数学专业蹭过课的软件工程专业的蒟蒻大学生来谈谈自己的见解。* *尽量避免生搬公式符号,多使用通俗的语言来说明。* ## 符号约定 我们使用$(a,b)$表示$a,b$这两个数的最大公因数,使用$[a,b]$表示$a,b$这两个数的最小公倍数。 我们使用$a\mid b$表示$a$能整除$b$,或者说$b$能被$a$整除; 我们使用$a\nmid b$表示$a$不能整除$b$,或者说$b$不能被$a$整除。 --- ## 算术基本定理 任何大于1的整数都可以被分解成若干个素数的幂的乘积,且不计素因子的排列顺序时分解方法是唯一的。 >例:$720=2^4\cdot 3^2\cdot 5^1$ 上面的操作叫做**素因数分解**。若将素因子从小到大排列,就得到了**标准素数分解式**。 --- ## 最大公因数和最小公倍数与素数分解式有什么联系呢? 举个例子: 我们尝试分解样例中的提到的一组数$12,15$: $12=2^2\cdot 3^1,\quad 15=3^1\cdot 5^1$ 为了方便下面的讨论,尽管$12$没有素因子$5$,$15$没有素因子$2$,但我们还是要把**非共有的素因子**写成$0$次幂的形式: $12=2^2\cdot 3^1\cdot 5^0,\quad 15=2^0\cdot 3^1\cdot 5^1$ 将两个数素数分解式中每个素因子的**指数部分**取两个中的**最小值**,就得到了两个数的**最大公因数**: $(12,15)=2^0\cdot 3^1\cdot 5^0=3$ 将两个数素数分解式中每个素因子的**指数部分**取两个中的**最大值**,就得到了两个数的**最小公倍数**: $[12,15]=2^2\cdot 3^1\cdot 5^1=60$ 倒着推我们可以发现,要使$(P,Q)=3$且$[P,Q]=60$,$P,Q$这两个数的素数分解式必须满足下面3个条件: >素因子$2$的指数的最大值为$2$,最小值为$0$.$\quad \Rightarrow$ 其中一个素数分解式中$2$的指数为$2$,而另一个为$0$; >素因子$5$的指数的最大值为$1$,最小值为$0$.$\quad \Rightarrow$ 其中一个素数分解式中$5$的指数为$1$,而另一个为$0$; >素因子$3$的指数的最大值为$1$,最小值为$1$.$\quad \Rightarrow$ 两个素数分解式中$3$的指数均为$1$; 像$2$和$5$这样的,指数在$x_0,y_0$的素数分解式中不同的素因子,能导致$P,Q$可变;而像$3$这样的,指数在$x_0,y_0$的素数分解式中相同的素因子,在$P,Q$中的指数一定是相同的,没法变化。 --- ## 计算方法 ### 如何快捷地寻找$x_0,y_0$的指数不同的素因子呢? 对$\dfrac{y_0}{x_0}$进行素因数分解,得到的**指数大于0的素因子**即是导致$P,Q$可变的素因子。 我们只需要统计这样的素因子的数量,就像把每种素因子看成不同的球,要放进$P,Q$这两个不同的袋子里,每一种素因子都有**放进**$P$和**放进**$Q$这两种选择。 假设$\dfrac{y_0}{x_0}$的指数大于0的素因子有$n$个,那么就能产生$2^n$对$P,Q$的组合。 ### 如果$x_0$不能整除$y_0$呢? 这表明不存在符合条件的$P,Q$. **反证**: 不妨假设存在符合条件的$P\in\mathbb Z_+$, 使得:$x_0$是$P$的因数,那么将有$x_0\mid P$; 使得:$y_0$是$P$的倍数,那么将有$P\mid y_0$; 根据整除的传递性,有$x_0\mid y_0$; 这个结论与题设矛盾,故假设不成立。 于是当$x_0\nmid y_0$时,我们输出`0`作为答案。 --- ## C++代码 ```cpp #include <iostream> int main() { int x, y; std::cin >> x >> y; if (y % x != 0) std::cout << 0; else { int quotient = y / x; int count = 0; //统计素因数的个数 int currentFactor = 2; //用来试验整除性的因数 while (quotient > 1) //等于1时标志着分解完毕 { if (quotient % currentFactor == 0) { count++; while (quotient % currentFactor == 0) quotient /= currentFactor;//若能整除就除到底 } currentFactor++; } std::cout << (1 << count);//使用位运算来产生2的方幂 } return 0; } ``` ## 谢谢阅读。 顺便宣传一波自己的经常挖坑不填的[知乎专栏](https://zhuanlan.zhihu.com/p/74477008)。