Lucas Theorem
Lucas's theorem calculates when is prime and may be far too large for factorials up to . It breaks one huge binomial coefficient into small coefficients formed by the base- digits of and .
We are given a prime and many queries with . For each query, calculate . Assume , so factorials from to fit in memory.
The usual formula needs , which is impossible to precompute. Even the factorial contains many factors of , so direct modular division is not valid.
Write and in base :
Lucas's theorem states
Every digit is smaller than , so each small coefficient can be calculated with factorials and inverse factorials modulo .
If any digit has , that small coefficient is zero, and the full answer is zero. This is the base- form of a carry obstruction.
Precompute fact[i] and invfact[i] for . Fermat's little theorem gives as its modular inverse.
Algorithm:
Each query uses one step per base- digit.
Think of Lucas's theorem as aligning the base- digits of and in columns. Every column contributes an independent small combination.
For , and . Starting from the least significant digit, the product is .
The input contains prime , the number of queries, and then pairs .
ki > ni: the complete answer becomes zero immediately.1. Precompute factorials modulo p from 0 to p - 1.
2. Precompute inverse factorials.
3. For each query n, k:
1. Set answer = 1.
2. While n > 0 or k > 0:
1. Set ni = n mod p and ki = k mod p.
2. If ki > ni, the answer is 0.
3. Multiply answer by C(ni, ki) modulo p.
4. Divide n and k by p.
3. Print answer.
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
long long p;
vector<long long> fact, invfact;
long long binpow(long long a, long long e) {
long long result = 1;
while (e > 0) {
if (e & 1) {
result = result * a % p;
}
a = a * a % p;
e >>= 1;
}
return result;
}
void build() {
fact.resize(p);
invfact.resize(p);
fact[0] = 1;
for (int i = 1; i < p; i++) {
fact[i] = fact[i - 1] * i % p;
}
invfact[p - 1] = binpow(fact[p - 1], p - 2);
for (int i = p - 1; i >= 1; i--) {
invfact[i - 1] = invfact[i] * i % p;
}
}
long long comb(int n, int k) {
if (k < 0 || k > n) {
return 0;
}
return fact[n] * invfact[k] % p * invfact[n - k] % p;
}
long long lucas(long long n, long long k) {
long long answer = 1;
while (n > 0 || k > 0) {
int ni = n % p;
int ki = k % p;
if (ki > ni) {
return 0;
}
answer = answer * comb(ni, ki) % p;
n /= p;
k /= p;
}
return answer;
}
void solve() {
int q;
cin >> p >> q;
build();
while (q--) {
long long n, k;
cin >> n >> k;
cout << lucas(n, k) << '\n';
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}