問題一覧 > 通常問題

No.181 A↑↑N mod M

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 58
作問者 : ぴろずぴろず
3 ProblemId : 472 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:38

問題文

$(A \upuparrows N) \; {\rm mod} \; M$を求めよ。
ただし、整数$a>0,n \geq 0$に対して$a \upuparrows n$を次のように定義する。

$\displaystyle a \upuparrows n = \begin{cases} 1 & (n = 0) \\ a^{(a \upuparrows (n-1))} & (otherwise) \end{cases}$

入力

$A$ $N$ $M$

1行目に3つの整数$A$,$N$,$M$がスペース区切りで与えられる。

$1 \leq A \leq 10^9$
$0 \leq N \leq 10^9$
$1 \leq M \leq 2000$

出力

$A \upuparrows N$を$M$で割った余りを1行に出力し、改行せよ。

サンプル

サンプル1
入力
3 2 100
出力
27

$3^{3^1} = 27 \equiv 27 \; (\rm mod \; 100)$ なので$27$が答えとなる。

サンプル2
入力
3 3 100
出力
87

$3 \upuparrows 3 = 3 ^ {3 \upuparrows 2} = 3 ^ {27} = 7625597484987 \equiv 87 \; (\rm mod \; 100)$ なので$87$が答えとなる。

サンプル3
入力
3 1000000000 2
出力
1

$3 \upuparrows n$がすべての整数$n(\geq 0)$について奇数であることが言える。

サンプル4
入力
87654321 0 1234
出力
1

$87654321 \upuparrows 0 = 1$

サンプル5
入力
1777 1855 1000
出力
97

サンプル6
入力
17893463 90476513 1458
出力
1091

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。