問題一覧 > 通常問題

No.1232 2^x = x

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 156
作問者 : t33ft33f / テスター : 37zigen37zigen
17 ProblemId : 3014 / 出題時の順位表
問題文最終更新日: 2019-07-28 18:10:13

問題文

素数$p_1, \dots, p_N$が与えられます。各$i$について$2^x = x \pmod {p_i}$を満たす$10^{18}$以下の正の整数$x$を一つ見つけてください。

入力

$N$
$p_1$
$\dots$
$p_N$

$1 \le N \le 1000$
$2 \le p_i \le 10^9$
$p_i$は素数

出力

$i$行目に$2^x = x \pmod {p_i}$を満たす$10^{18}$以下の正の整数 $x$ を出力してください。
存在しない場合は代わりに$-1$を出力してください。
解が複数ある場合はどれを出力しても構いません。

サンプル

サンプル1
入力
3
5
3
2
出力
3
4
2

$2^3 = 8 = 3 \pmod 5$, $2^4 = 16 = 4 \pmod 3$, $2^2 = 4 = 2 \pmod 2$ です。

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