ストーリー

RSA 暗号は、世界で広く使われている公開鍵暗号アルゴリズムです。

高橋くんは自分でも RSA 暗号を使ってみようと思いました。

そのためには鍵を作ることが必要です。

RSA 暗号の鍵生成は以下のような手順で行います。

鍵生成

RSA 暗号では、鍵を生成するために適当な素数 p,qp, q と、自然数 ee を選びます。

自然数 nn を、

  • n=pqn = pq

と置きます。

ここで、 φ=ϕ(n)=(p1)(q1)\varphi = \phi(n) = (p - 1)(q - 1) とすると、 eeφ\varphi 未満の自然数で、 φ\varphi と互いに素である必要があります。( ϕ(n)\phi(n) はオイラーのφ関数 )

自然数 dd を、

  • de1modφd \equiv e^{-1} \mod \varphi

と置きます。

φ\varphi は多くの場合合成数であるため、 dd の計算は(拡張)ユークリッドの互除法により行います。

このようにして計算された値を使い、公開鍵と秘密鍵を作成することができます。

  • 公開鍵: (n,e)(n, e)
  • 秘密鍵: (n,d)(n, d)

問題文

相異なる素数 p,qp, q と正整数 ee が与えられます。

秘密鍵 (n,d)(n, d) を生成し、 nndd を出力してください。

ただし、 n=pqn = pq とし、 ddde1mod(p1)(q1)d \equiv e^{-1} \mod (p - 1)(q - 1) となるような最小の非負整数とします。

制約

  • 2p,q1092 \le p, q \le 10^9
  • p,qp, q は素数であり、 pqp \ne q である
  • 2e(p1)(q1)2 \le e \le (p - 1)(q - 1)
  • ee(p1)(q1)(p - 1)(q - 1) は互いに素である
  • 入力はすべて整数である

入力

p q ep\ q\ e

出力

  • 11 行目に nn を出力せよ。
  • 22 行目に dd を出力せよ。

入出力例

入力例1
5 11 3
出力例1
55
27

p=5,q=11,e=3p = 5, q = 11, e = 3 のとき、 n=55,d=27n = 55, d = 27 となります。

入力例2
97 997 64295
出力例2
96709
10007
入力例3
998244353 998244853 5
出力例3
996492287418565109
199298457084415181

出力は 3232 ビット整数で表される範囲を超える可能性があります。

Submit


Go (1.21)