P12620 [ICPC 2025 NAC] A Totient Quotient

对于一个正整数 $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)$ 表示 $p$ 的最高幂次，使得 $p^{\nu_p(k)}$ 能整除 $k$（例如，$\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)\left(p_i^{\nu_{p_i}(k)-1}\right)\right].$$ 《美国数学月刊》（Li 等人，《形如 $\phi(m^2)/\phi(n^2)$ 的正有理数》，128(2)，2021 年）最近的一期证明了以下关于欧拉商的事实：对于任意一对正整数 $a$、$b$，存在唯一的一对正整数 $m$、$n$ 满足： 1. $\frac{a}{b} = \frac{\phi(m^2)}{\phi(n^2)}$； 2. 如果一个质数 $p$ 整除乘积 $mn$，则 $\nu_p(m) \neq \nu_{p}(n)$； 3. $\gcd(m,n)$ 是无平方因子的：即对于每个质数 $p$，$\gcd(m,n)$ 不被 $p^2$ 整除。 条件 2 和 3 保证了 $m$ 和 $n$ 是满足条件 1 的唯一最小正整数对。 你希望通过数值验证这一结论。编写一个程序，输入两个整数 $a$ 和 $b$，输出对应的 $m$ 和 $n$。

输入仅有一行，包含两个以空格分隔的整数 $a$ 和 $b$（$1 \leq a, b \leq 10\,000$）。这两个整数保证互质。此外，$a$ 和 $b$ 的选择会使得输出的 $m$ 和 $n$ 均小于 $2^{63}$。

输出两个满足《美国数学月刊》定理中所有三个条件的正整数 $m$ 和 $n$，以空格分隔。保证 $m, n < 2^{63}$。

翻译由 DeepSeek V3 完成