QOJ.ac

QOJ

実行時間制限: 1 s メモリ制限: 2048 MB 満点: 100

#11356. 欧拉函数商

統計

对于正整数 $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$ 满足:

  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 \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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.