No.181 A↑↑N mod M
ぴろず問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。