No.2207 pCr検査

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題（複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 32
作問者 : 👑

testestest / テスター :

tatyam

0 ProblemId : 8253 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2022-07-13 01:47:47

問題文

整数 $N$ が与えられます。素数 $p$ と非負整数 $r$ であって、二項係数 ${}_pC_r$ が $N$ と等しくなるものは存在しますか？

入力

 $k$ 
 $p_1$   $e_1$ 
 $\vdots$ 
 $p_k$   $e_k$

$N$ は素因数分解した形で与えられ、 $N=\prod_{i=1}^{k}p_i^{e_i}$ である
$k\geq 1$
$2\leq p_1 < \ldots < p_k \leq 10^7$
$1\leq e_i\leq 10^7$

なお、この制約から、

N={}_pC_r

となる素数

p

と非負整数

r

が存在するとき、特に

p\leq 10^{49}

であるものが存在することが保証される。

出力

$N={}_pC_r$ を満たす $10^{49}$ 以下の素数 $p$ と非負整数 $r$ が存在するとき、 $p,r$ の順に空白区切りで出力し改行せよ。解が複数ある場合、どれを出力しても正解となる。
そのような $p,r$ が存在しないなら、かわりに -1 -1 と出力し改行せよ。
末尾に余計な出力があっても正解となる。

サンプル

サンプル1

入力

2
2 1
5 1

出力

5 2

5 3 などの出力でも正解になります。

サンプル2

入力

2
2 2
5 1

出力

-1 -1

${}_pC_r=20$ を満たす $(p,r)$ は存在しません。 $p$ は素数でなければならないことに注意してください。

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