No.1232 2^x = x
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 220
作問者 :
t33f
/ テスター :
37zigen
タグ : / 解いたユーザー数 220
作問者 :
t33f
/ テスター :
37zigen
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。