| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 256 MB | 1 | 0 | 0 | 0.000% |
For his number theory homework, Busy Beaver is given $T$ pairs of a large prime $p$ and an integer $x$. For each pair, Busy Beaver needs to find a subset of $\{1,\frac 12,\frac 13,\cdots,\frac 1{5000}\}$ of size at most $S$ whose sum is equal to $x$ modulo $p$. Can you help him find such subsets?
A rational number $\frac ab$ is equal to $x$ modulo $p$ if $a \equiv bx \pmod p$.
The first line contains two integers $T$ and $S$ (1ドル \le T \le 1000,ドル 150ドル \le S \le 5000$), indicating the number of testcases and the maximum size of the subset.
Each of the next $T$ lines contains two integers $p$ and $x$ (10ドル^8 \le p \le 10^{18},ドル 0ドル \le x \le p-1$), where $p$ is prime.
For each testcase, output one line indicating the answer. Start with some integer $k$ (0ドル \le k \le S$), indicating the size of the subset, and then follow with $k$ distinct integers $a_1,\dots,a_k$ in increasing order (1ドル \le a_1 < a_2 < \dots < a_k \le 5000$).
Your output should satisfy $\frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_k} \equiv x \pmod p$.
It can be proven that for all $p,ドル $x$ satisfying the input constraints, such a subset always exists.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $T \le 10,ドル $p \le 10^9$. |
| 2 | 20 | $T \le 10,ドル $p \le 10^{15},ドル $S = 5000$. |
| 3 | 30 | $S = 5000$. |
| 4 | 40 | No additional constraints. |
4 150 998244353 0 1000000007 1 1000000007 500000004 1000000007 642833014
0 1 1 1 2 3 1 19 2025
In the first test case, the empty subset sums to $x = 0$ modulo $p = 998244353$.
In the second test case, $\frac{1}{1} \equiv 1 \pmod {1000000007}$.
In the third test case, $\frac{1}{2} \equiv 500000004 \pmod {1000000007}$.
In the fourth test case, $\frac{1}{1} + \frac{1}{19} + \frac{1}{2025} \equiv 642833014 \pmod {1000000007}$.
University > MIT > M(IT)^2 > M(IT)^2 Winter 2025 Tournament > Advanced Round 1 5번