問題一覧 > 通常問題

No.2011 Arbitrary Mod (Hidden)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 53
作問者 : Kiri8128Kiri8128 / テスター : 👑 platinumplatinum
14 ProblemId : 8031 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-07 02:02:00

問題文

$(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$
$a$ はテストケースごとに予め決まっていますが、入力では与えられないことに注意してください。

出力

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。