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$），
所以 $ \gcd(a,b) = \gcd(a,a\bmod b)$ ,而这，就是欧几里得算法的核心内容。(终于结束了)下面给出欧几里得算法的代码：

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})}$$

将以上两个式子相乘，可以得到:

$ \large \gcd(a,b)\times \operatorname{lcm}(a,b)=a\times b$

将上面的式子进行移项，就终于得到了这个重要的计算方法（呼，累死我了）：

$\large \operatorname{lcm}(a,b) = a\times b \div \gcd(a,b)$

题解思路

那么，这道题基本的知识都讲完了，总结一下思路：
首先我们可以枚举$P$，那么$Q$可通过已经给的最小公倍数和最大公约数来求，然后再算出本身这两个数的最小公倍数和最大公约数，判断它们是否相等。

代码

#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;
}