問題一覧 > 通常問題

No.2207 pCr Test

レベル : / AI推定難易度 : 2050 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 32
作問者 : testestest / テスター : tatyam
お気に入りにしたユーザー ProblemId : 8253 / 自分の提出
問題文最終更新日: 2022-07-13 01:47:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 375 (順位表) の他の問題:

Problem Statement

You are given an integer $N$. Do there exist a prime $p$ and a non-negative integer $r$ such that the binomial coefficient ${}_pC_r$ is equal to $N$?

Input

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

  • $N$ is given in its prime factorized form, where $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$
Under these constraints, it is guaranteed that if there exist a prime $p$ and a non-negative integer $r$ with $N={}_pC_r$, then in particular there exists one with $p\leq 10^{49}$.

Output

If there exist a prime $p$ not exceeding $10^{49}$ and a non-negative integer $r$ satisfying $N={}_pC_r$, print $p,r$ in this order, separated by a space, followed by a newline. If there are multiple solutions, any of them will be accepted.
If no such $p,r$ exist, print -1 -1 instead, followed by a newline.
Extra output at the end will still be accepted.

Sample

Sample 1
Input
2
2 1
5 1
Output
5 2

Outputs such as 5 3 will also be accepted.

Sample 2
Input
2
2 2
5 1
Output
-1 -1

There is no $(p,r)$ satisfying ${}_pC_r=20$. Note that $p$ must be prime.

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