問題一覧 > 通常問題

No.2007 Arbitrary Mod (Easy)

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

問題文

$a^n$ を $M$ で割った余りを出力してください。

$a$ と $n$ は入力で与えられますが、 $M$ はあなたが好きなものを選んで良いです。 ただし $M$ は整数で $10^7 \le M \le 10^{18}$ を満たす必要があります。

入力

$a\ n$

【制約】

  • $a,\ n$ は整数
  • $2 \le a \le 1000$
  • $2 \le n \le 10^{18}$

出力

$M$
$ans$

$1$ 行目に $M$ を出力してください。 $M$ は整数で、かつ $10^7 \le M \le 10^{18}$ を満たす必要があります。
$2$ 行目に問題の答え $ans$ 、すなわち $a^n$ を $M$ で割った余りを出力してください。
最後に改行してください。

出力の $1$ 行目で与えた $M$ に対して、 $a^n$ を $M$ で割った余りが出力の $2$ 行目で与えた $ans$ と一致した場合に AC が得られます。

サンプル

サンプル1
入力
5 3
出力
998244353
125

あなたは好きな $M$ として $998244353$ を選び $1$ 行目に出力しました。
$5^{3} = 125$ を $M$ で割った余りである $125$ を $2$ 行目に出力しました。

サンプル2
入力
2 30
出力
10000000
3741824

あなたは $M=10^7$ を選び $1$ 行目に出力しました。
$2^{30} = 1073741824$ なので、これを $10^7$ で割った余りである $3741824$ を $2$ 行目に出力すると AC できます。

ほかにも、例えば $1$ 行目で $1073741824$ を、 $2$ 行目に $0$ を出力しても AC を得ることができます。

サンプル3
入力
999 12345678987654321
出力
998244353
877641551

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