nCr Modulo a Small Prime (Huge n)
hardMath & Number Theory+40 XPTime limit 2s
Compute nCr mod p where n and r can be as large as 10¹⁸ but the prime p is small. Factorials up to n are impossible to precompute here — and since n can exceed p, n! would be 0 mod p anyway, so the usual formula breaks. If r > n the answer is 0.
Input:
- line 1:
q p— the number of queries and the prime modulus - next
qlines: two integersn r
Output: q lines — nCr mod p.
Constraints: 1 ≤ q ≤ 10⁴, 2 ≤ p ≤ 10⁵ and p is prime, 0 ≤ n, r ≤ 10¹⁸.
Think about it: Lucas' theorem. Write n and r in base p: n = n₀ + n₁p + n₂p² + …, same for r. Then nCr ≡ (n₀ C r₀) · (n₁ C r₁) · … (mod p), where any factor with rᵢ > nᵢ makes the whole answer 0. Each small nᵢ C rᵢ (with nᵢ < p) comes from factorials up to p − 1 and Fermat inverses.
Sample input 1
3 7 10 3 7 7 5 6
Sample output 1
1 1 0
Sample input 2
2 2 1000000000000000000 500000000000000000 5 1
Sample output 2
0 1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).