No.2011 Arbitrary Mod (Hidden)
タグ : / 解いたユーザー数 56
作問者 :
Kiri8128
/ テスター :
platinum
問題文
$(a^2-398)^{2^n}$ を $M$ で割った余りを出力してください。
・・・おっと、諸事情により $a$ と $M$ が入力で与えられないことになりました。 $a$ は予め決まっているのですが、 $M$ はあなたが好きなものを選んで良いです。 ただし $M$ は整数で $10^7 \le M \le 10^{18}$ を満たす必要があります。
なお指数計算は上から計算することに注意してください。すなわち $x^{y^z} = x^{(y^z)}$ です（ $(x^y)^z$ ではありません ）。
入力
$n$
【制約】
- $a,\ n$ は整数
- $20\le a\le 5000$
- $100\le n \le 10^9$
出力
$M$ $ans$
$1$ 行目に $M$ を出力してください。 $M$ は整数で、かつ $10^7 \le M \le 10^{18}$ を満たす必要があります。
$2$ 行目に問題の答え $ans$ 、すなわち $(a^2-398)^{2^n}$ を $M$ で割った余りを出力してください。
最後に改行してください。
テストケースごとに予め決まっている $a$ および出力の $1$ 行目で与えた $M$ に対して、 $(a^2-398)^{2^n}$ を $M$ で割った余りが出力の $2$ 行目で与えた $ans$ と一致した場合に AC が得られます。
サンプル
サンプル1
これは説明用の小さいケースのため $100 \le n \le 10^9$ の制約を満たしていません。実際のテストケースにも含まれていません。また仮に制約が緩かったとしても、後述のとおり、必ず AC が得られる訳ではありません。
入力
1
出力
998244353 4
あなたは $M$ として $998244353$ を選びました。
$a$ は入力に与えられませんが、もしこのケースにおいて $a=20$ であれば、
求めるものは $(20^2-398)^{2^1}=2^2=4$ を $998244353$ で割った余りである $4$ です。これはあなたの $2$ 行目の出力に一致するため正解となります。
もし例えば $a=21$ であれば求めるものは $1849$ となり、不正解になってしまうことに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。