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
2
3
int gcd(int a,int b){
return b==0 ? a : gcd(b,a%b);
}


下面我们来讲最小公倍数的算法,最小公倍数可以通过最大公约数来求.

最小公倍数

首先我们介绍这样一个定理——算术基本定理:

每一个正整数都可以表示成若干整数的乘积,这种分解方式在忽略排列次序的条件下是唯一的。

这个有一个通式 \(\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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<iostream>
#include<cmath>
typedef long long LL;

using namespace std;

LL gcd(int a,int b){ //最大公约数的算法
return b==0 ? a : gcd(b,a%b);
}


int main()
{
LL n,m,ans = 0;
cin>>n>>m;


for(int i=1;i<=sqrt(m*n);i++){ //枚举到sqrt个即可
if(n==m){
ans = 1;
break;
}
int j = m*n/i;
LL x = 0,y = 0;
LL cnt = gcd(i,j);
if(cnt == n && i*j/cnt == m) //i*j/cnt 是算最大公约数的算法
ans += 2;
}

cout<<ans<<endl;
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!