对于正整数 $k$,欧拉函数 $\phi(k)$ 定义为小于或等于 $k$ 且与 $k$ 互质的正整数的个数。例如,$\phi(9) = 6$,$\phi(24) = 8$,以及 $\phi(1) = 1$。(提醒:两个正整数 $a$ 和 $b$ 的最大公约数(gcd)是同时整除 $a$ 和 $b$ 的最大正整数。若两个正整数的 gcd 为 1,则称它们互质。)
欧拉乘积公式根据 $k$ 的质因数分解给出了 $\phi(k)$ 的值。对于质数 $p$,令 $\nu_p(k)$ 为整除 $k$ 的 $p$ 的最高幂次(例如,$\nu_2(48) = 4$,$\nu_3(48) = 1$,以及 $\nu_5(48) = 0$)。如果 $k$ 是质因数幂的乘积,$k = \prod_{i=1}^j p_i^{\nu_{p_i}(k)}$(其中乘积仅包含 $\nu_{p_i}(k) > 0$ 的质数 $p_i$),则:
$$\phi(k) = \prod_{i=1}^j \left[ (p_i - 1) p_i^{\nu_{p_i}(k)-1} \right]$$
《美国数学月刊》(The American Mathematical Monthly)最近的一期(Li 等人,Positive Rational Numbers of the Form $\phi(m^2)/\phi(n^2)$,128(2),2021)证明了关于欧拉函数商的以下事实:对于任意一对正整数 $a, b$,存在唯一的一对正整数 $m, n$ 满足:
- $\frac{a}{b} = \frac{\phi(m^2)}{\phi(n^2)}$;
- 如果质数 $p$ 整除乘积 $mn$,则 $\nu_p(m) \neq \nu_p(n)$;
- $\gcd(m, n)$ 是无平方因子数:即对于每个质数 $p$,$\gcd(m, n)$ 不能被 $p^2$ 整除。
条件 2 和 3 保证了 $m$ 和 $n$ 是满足条件 1 的唯一最小正整数对。
你需要通过数值验证这一结论。编写一个程序,输入两个整数 $a$ 和 $b$,输出对应的整数对 $m, n$。
输入格式
输入仅一行,包含两个空格分隔的整数 $a$ 和 $b$ ($1 \le a, b \le 10\,000$)。保证这两个整数互质。此外,选择 $a$ 和 $b$ 时保证输出的 $m$ 和 $n$ 小于 $2^{63}$。
输出格式
输出满足《美国数学月刊》定理中所有三个条件的两个正整数 $m$ 和 $n$,中间用空格分隔。保证 $m, n < 2^{63}$。
样例
输入格式 1
9 13
输出格式 1
18 13
输入格式 2
19 47
输出格式 2
13110 18612