A Totient Quotient

시간 제한1초메모리 제한2048 MB

요약
기약분수 a/b가 주어질 때 a/b = phi(m^2)/phi(n^2)를 만족하는 최소의 순서쌍 m, n을 구한다.
난이도

어려움10점 중 9점

유형
정수론, 수학, 구현
정답자
아직 제출이 없습니다

문제

For a positive integer kk, Euler's totient function ϕ(k)\phi(k) is defined as the number of positive integers less than or equal to kk and relatively prime to kk. For example, ϕ(9)=6\phi(9) = 6, ϕ(24)=8,\phi(24) = 8, and ϕ(1)=1\phi(1) = 1. (As a reminder, the greatest common divisor (gcd) of two positive integers aa and bb is the greatest positive integer that divides both aa and bb. Two positive integers are relatively prime if their gcd is 11.)

Euler's product formula gives the value of ϕ(k)\phi(k) in terms of the prime factorization of kk. For a prime pp, let ν_p(k)\nu\_p(k) be the highest power of pp which divides kk (so for example, ν_2(48)=4\nu\_2(48) = 4, ν_3(48)=1\nu\_3(48)=1, and ν_5(48)=0\nu\_5(48)=0). If kk is a product of powers of prime factors, k=∏_i=1jp_iν_p_i(k)k = \prod\_{i=1}^j p\_i^{\nu\_{p\_i}(k)} (where the product only includes primes p_ip\_i with ν_p_i(k)>0\nu\_{p\_i}(k) > 0), then \phi(k) = \prod\_{i=1}^j \left\[(p\_i - 1)\left(p\_i^{\nu\_{p\_i}(k)-1}\right)\right].

A recent edition of The American Mathematical Monthly (Li et al., Positive Rational Numbers of the Form ϕ(m2)/ϕ(n2)\phi(m^2)/\phi(n^2), 128(2), 2021) proved the following fact about totient quotients: for any pair of positive integers aa, bb there is a unique pair of positive integers mm, nn for which:

  1. ab=ϕ(m2)ϕ(n2);\frac{a}{b} = \frac{\phi(m^2)}{\phi(n^2)};
  2. if a prime pp divides the product mnmn, then ν_p(m)≠ν_p(n)\nu\_p(m) \neq \nu\_{p}(n);
  3. gcd⁡(m,n)\gcd(m,n) is square-free: that is, for every prime pp, gcd⁡(m,n)\gcd(m,n) is not divisible by p2p^2.

Conditions 2 and 3 guarantee that mm and nn are the unique smallest pair of positive integers satisfying condition 1.

You'd like to verify this claim numerically. Write a program which takes as input two integers aa and bb and outputs the corresponding pair m,nm, n.

입력

The only line of input contains two space-separated integers aa and bb (1≤a,b≤10,000 1 \leq a, b \leq 10\\,000). These two integers are guaranteed to be relatively prime. Additionally, aa and bb will be chosen so that output values mm and nn are less than 2632^{63}.

출력

Print the two positive integers mm and nn satisfying all three of the conditions of The American Mathematical Monthly's theorem, separated by a space. It is guaranteed that m,n<263 m, n < 2^{63}.

예제2

  1. 예제 1

    입력
    9 13
    
    예상 출력
    18 13
    
  2. 예제 2

    입력
    19 47
    
    예상 출력
    13110 18612