Định Lý Lucas

Buổi 58 — Modular Arithmetic
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề 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}$
Draft saved