题面
题目描述
输入两个正整数 $x_0, y_0$，求出满足下列条件的 $P, Q$ 的个数：
- $P,Q$ 是正整数。
- 要求 $P, Q$ 以 $x_0$ 为最大公约数，以 $y_0$ 为最小公倍数。
试求：满足条件的所有可能的 $P, Q$ 的个数。
输入格式
一行两个正整数 $x_0, y_0$。
输出格式
一行一个数，表示求出满足条件的 $P, Q$ 的个数。
输入输出样例 #1
输入 #1
3 60输出 #1
4说明/提示
$P,Q$ 有 $4$ 种：
- $3, 60$。
- $15, 12$。
- $12, 15$。
- $60, 3$。
对于 $100\%$ 的数据，$2 \le x_0, y_0 \le {10}^5$。
【题目来源】
NOIP 2001 普及组第二题
题解
一道数论题。
首先判断$x_0$是否为$y_0$的约数。如果不是，由最小公倍数的约数必定包含最大公约数可知，数对$P, Q$不可能存在，则输出$0$。
其次，我们考虑数对$P, Q$的生成方式。对$x_0, y_0$进行质因数分解，设为：
$x_0={p_1}^{m_1}*{p_2}^{m_2}*\cdots*{p_j}^{m_j}$
$y_0={p_1}^{m_1}*{p_2}^{m_2}*\cdots*{p_j}^{m_j}*{q_1}^{n_1}*{q_2}^{n_2}*\cdots*{q_k}^{n_k}$
其中$q_1, q_2, \cdots, q_k$可能与$p_1, p_2, \cdots, p_j$的部分或全部重合。
由题意，得到$P, Q$生成的如下约束条件：
①最大公约数是$x_0$，则$P, Q$的公约数不能出现除{p_1}^{m_1}, {p_2}^{m_2}, \cdots*, {p_j}^{m_j}及它们的低次幂以外的约数。
反例：$x_0=3, y_0=60$，构造了$P=6, Q=30$（将$y_0$的一个约数$2$转移给$x_0$），此时$P, Q$的最大公约数是$6$而非$3$。
②最小公倍数是$y_0$，则$P, Q$中均不可能出现除$p_i, q_i$以外的约数。
综上，我们可以得出数对$P, Q$的生成方式：
- 前提：$(x_0, y_0)$是一组合法的$(P, Q)$。否则$(P, Q)$不存在。
- 对$\frac{y_0}{x_0}$的结果进行质因数分解，得到
$\frac{y_0}{x_0}={q_1}^{n_1}*{q_2}^{n_2}*\cdots*{q_k}^{n_k}$
- 将上式中的${q_i}^{n_i}$视为一组质因数，将完整的一组或多组质因数由$y_0$转移至$x_0$。
- 因此，答案为$2^k$。（分步乘法原理：每一组质因数都有“转移”或“不转移”两种状态。）
完整代码如下。
#include<cstdio>
#include<cmath>
int x,y,cnt=0,s[100001],f=2;
bool p(int x)
{
if(s[x]||x==2) return false;
for(int i=2;i<=sqrt(x)+1;i++)
{
if(!(x%i)) return true;
}
s[x]=1; //质数判断结果记忆化
return false;
}
int main()
{
scanf("%d%d",&x,&y);
if(y%x)
{
printf("0");
return 0;
}
y/=x;
while(y>1)
{
for(int i=f;i<=y;i++)
{
if(y%i||p(i)) continue;
while(!(y%i)) y/=i;
f=i; //质因数分解结果记忆化
cnt++;
break;
}
}
printf("%d",1<<cnt); //等价于pow(2,cnt);
return 0;
}