Định Lý Lucas
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề bài
Cho $T$ truy vấn, mỗi truy vấn gồm ba số $N, K, P$, trong đó $P$ là một số nguyên tố nhỏ. Hãy tính $\binom{N}{K} \bmod P$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $T$ và $P$ ($1 \le T \le 10^4$, $2 \le P \le 10^5$, $P$ nguyên tố).
- $T$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $N, K$ ($0 \le K \le N \le 10^{18}$).
Dữ liệu ra
Với mỗi truy vấn, in ra $\binom{N}{K} \bmod P$.
Ví dụ
| Input | Output |
|---|---|
| 2 13 10 3 1000 500 |
3 0 |
Giới hạn
- $1 \le T \le 10^4$
- $2 \le P \le 10^5$ ($P$ nguyên tố)
- $0 \le K \le N \le 10^{18}$
Community Discussion