No.613 Solitude by the window
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 :
夕叢霧香(ゆうむらきりか)
/ テスター :
uwi
タグ : / 解いたユーザー数 22
作問者 :
夕叢霧香(ゆうむらきりか)
/ テスター :
uwi
問題文最終更新日: 2017-12-13 12:49:33
問題文
最初石が2個ある。 この石は、1秒経つ度に、それぞれがその時点での石の個数+4個に同時に分裂する。 例えば、開始から1秒後には$2 \times (2 + 4) = 12$個の石があり、 さらに1秒後には$12 \times (12 + 4) = 192$個の石がある状態になる。 この時、$N$秒後の石の個数を、$\text{mod}~M$ ($M$は素数)で求めてね。
入力
N M
$N$は整数で、$1\le N \le 10^{18}$。
$M$は素数で、$2\le M \le 1100000000=1.1\times 10^9$。
出力
最後に改行してね。
サンプル
サンプル1
入力
2 10007
出力
192
サンプル2
入力
100000000 5
出力
2
$n$秒後の石の個数を$a_n$とすると、任意の0以上の整数$n$に対して、$a_n \equiv 2 \pmod 5$が成り立つわ。
サンプル3
入力
1000000000000000000 1000000007
出力
688982865
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。