P1029 [NOIP2001 普及组] 最大公约数和最小公倍数
题目
题目描述
输入两个正整数\(x_0,
y_0\),求出满足下列条件的\(P,
Q\)的个数:
1. \(P,Q\) 是正整数。 2. 要求 \(P, Q\) 以 \(x_0\)为最大公约数,以\(y_0\)为最小公倍数。
试求:满足条件的所有可能的\(P, Q\)的个数。 ## 输入格式 一行两个正整数\(x_0, y_0\)。 ## 输出格式 一行一个数,表示求出满足条件的\(P, Q\)个数。
知识讲解
这一题是关于最大公约数(gcd)和最小公倍数(lcm)的,首先要算最大公约数,最好的算法是欧几里得算法(辗转相除法)然而本人是个蒟蒻,所以还是要来证明一下的:
### 最大公约数 设 \(a=bk+c\) 则有 \(c= a\bmod b\) ,设有一个数 \(d \mid a~,d \mid
b\)(这个符号表示前者是后者的因数,能整除), 则存在 \(c=a-bk\) , \(\dfrac{c}{d} = \dfrac{a-b}{d}k\)。
显而易见,\(\dfrac{c}{d}\)
为整数,所以对于 \(a\) 与 \(b\) 的最大公约数为 \(a\bmod b\) 的最大公约数(因为c为\(c= a\bmod b\)),
所以 $ (a,b) = (a,ab)$
,而这,就是欧几里得算法的核心内容。(终于结束了)下面给出欧几里得算法的代码:
1 |
|
下面我们来讲最小公倍数的算法,最小公倍数可以通过最大公约数来求.
最小公倍数
首先我们介绍这样一个定理——算术基本定理:
每一个正整数都可以表示成若干整数的乘积,这种分解方式在忽略排列次序的条件下是唯一的。
这个有一个通式 \(\large x=p_1^{k_1}p_2^{k_2}p_3^{k_3}\dots b p_s^{k_s}\)
设 \[\large a=p_1^{k_{a_1}}p_2^{k_{a_2}}p_3^{k_{a_3}} \dots p_s^{k_{a_s}} ,\large b=p_1^{k_{b_1}}p_2^{k_{b_2}}p_3^{k_{b_3}}\dotsb p_s^{k_{b_s}}\]
可以得到,最大公约数为:
\[\large
p_1^{\min(k_{a_1},k_{b_1})}p_2^{\min(k_{a_2},k_{b_2})}\dotsb
p_s^{\min(k_{a_s},k_{b_s})}\]
最小公倍数为:
\[\large
p_1^{\max(k_{a_1},k_{b_1})}p_2^{\max(k_{a_2},k_{b_2})}\dotsb
p_s^{\max(k_{a_s},k_{b_s})}\]
将以上两个式子相乘,可以得到: > $ (a,b)(a,b)=ab$
将上面的式子进行移项,就终于得到了这个重要的计算方法(呼,累死我了):
\(\large \operatorname{lcm}(a,b) = a\times b \div \gcd(a,b)\)
题解思路
那么,这道题基本的知识都讲完了,总结一下思路: 首先我们可以枚举\(P\),那么\(Q\)可通过已经给的最小公倍数和最大公约数来求,然后再算出本身这两个数的最小公倍数和最大公约数,判断它们是否相等。
代码
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!