LG#P1029. [NOIP 2001 普及组] 最大公约数和最小公倍数问题

[NOIP 2001 普及组] 最大公约数和最小公倍数问题

P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题

题目描述

\hspace{15pt}输入两个正整数 x0,y0x_0,y_0,求出满足下列条件的 p,qp,q 的个数:

1. p,q{\hspace{20pt}}_\texttt{1.}\,p,q 是正整数;

2. {\hspace{20pt}}_\texttt{2.}\,要求 p,qp,q 以 x0x_0 为最大公约数,以 y0y_0 为最小公倍数。

\hspace{15pt}试求满足条件的所有可能的 p,qp,q 的个数。

输入格式

\hspace{15pt}在一行上输入两个正整数 x0,y0(2≦x0,y0≦105)x_0,y_0 \left(2 \leqq x_0,y_0 \leqq 10^5 \right)。

输出格式

\hspace{15pt}在一行上输出一个整数,代表满足条件的 p,qp,q 的个数。若不存在满足条件的 p,qp,q,输出 00。

测试样例

3 60

4

样例 1 解释

\hspace{15pt}满足条件的 p,qp,q 共有 44 种方案:

1. (p,q)=(3,60){\hspace{20pt}}_\texttt{1.}\,(p,q)=(3,60);

2. (p,q)=(15,12){\hspace{20pt}}_\texttt{2.}\,(p,q)=(15,12);

3. (p,q)=(12,15){\hspace{20pt}}_\texttt{3.}\,(p,q)=(12,15);

4. (p,q)=(60,3){\hspace{20pt}}_\texttt{4.}\,(p,q)=(60,3)。