Ax = By = z^C

想定解

この問題は素因数分解を利用することで解くことができます．

最初に具体例で説明します．サンプル 1 を題材とします．サンプル 1 では $(A, B, C) = (24, 90, 2)$ が与えられますが，$A, B$ を素因数分解すると下記のようになります．

• $24 = 2^3 \times 3$
• $90 = 2 \times 3^2 \times 5$

これを与式に代入すると次式が得られます．

• $2^3 \times 3 \times x = 2 \times 3^2 \times 5 \times y = z^2$

上式の左辺・中辺との等号を満たすように $z$ を（可能な範囲で）素因数分解することを考えます．例えば，素因数 $2$ について考えると，左辺の $2$ の指数が $3$ であることから「$z^2$ の素因数 $2$ の指数が $3$ 以上である」が要請され，つまり「$z$ の $2$ の指数が $2$ 以上である」が要請されます．残りの素因数についても同様にすると，$z$ は次のように書き表すことができます．

• $z = 2^2 \times 3 \times 5 \times k \,\,\,\,(k は自然数)$

よって，$k = 1$ のとき $z$ の最小値が得られるので，答えは $60$ と求められます．

次に，実装について説明します．例えば，下記の $3$ ステップで解けます．

1. まずは整数 $A, B$ を素因数分解します．試し割り法を使えば時間計算量 $O(\sqrt{A} + \sqrt{B})$ で計算可能です．このとき，素因数 $f$ と指数 $n$ のペア $(f, n)$ を保持するように素因数分解しておくと後で便利です．

2. 具体例でも触れた通り，$A, B$ に含まれる素因数 $f$ の指数 $n_A, n_B$ は大きい方のみ使用すれば十分なので，$n = \mathrm{max}(n_A, n_B)$ などとして素因数分解の結果をマージします．漏れが発生しないように注意してください．

3. 以上の結果と整合するように $z$ を素因数分解します．素因数 $f$ の指数 $n$ について，$m = \lceil \frac{n}{C} \rceil$ を計算することで $z$ における素因数 $f$ の指数の下限が $m$ と求められます（$\lceil x \rceil$ は天井関数です）．よって，素因数 $f$ について掛け算を $m$ 回行い，これをすべての素因数 $f$ について繰り返せば答えを求められます．オーバーフローしないように $1000000007$ による剰余計算を適宜行う必要があることに注意してください．