Lucas’ Theorem. Wilson’s Theorem

Lucas’ TheoremStatement:C(N, K) % MOD = (C(n0, k0) * C(n1, k1) * … * C(nm-1, km-1)) % MODn0, n1, … nm-1andk0, k1, … km-1are representations of the numbersNandKin the scale of notation with baseMOD. In other words:N = n0* MOD0+ n1* MOD1+ … + nm-1* MODm-1K = k0* MOD0+ k1* MOD1+ … + km-1* MODm-1C(N, K)isBinomial coefficient(number of ways to chooseKelements from a set ofNelements).Conditions:MODis a prime number (look at the end of the article to know what can we do with not primeMOD), and you should be able to calculateC(ni, ki) % MOD, where(0 ≤ ni, ki< MOD).Advices:this theorem is very useful in caseN ≥ MOD, otherwise it’s better to use formulaC(N, K) = N! / ((N – K)! * K!)and tricks #2 or #3 fromthere. IfN ≥ MODthenN! % MOD = 0, whenC(N, K) % MODis not necessary equals to0.Realization:let’s see how can we get representation of some numberNin the scale of notation with baseMOD:vector<int> getRepresentation(int N) {
vector<int> res;
while (N > 0) {
res.push_back(N % MOD);
N /= MOD;
}
return res;
}Letnwill be representation ofNandkwill be representation ofK. They are not necessary have the same length. IfK > Nwe can easily say thatC(N, K) = 0. Otherwisekhas less or equal length thann. To make them the same length we can add some extra zeroes tokand make them both of length ofn, or we can take only some first elements ofnand make them both of length ofk. The second way has more sense becauseC(ni, 0) = 1.So the main part of code looks like:vector<int> n = getRepresentation(N);
vector<int> k = getRepresentation(K);
long long res = 1;
for (int i = 0; i < k.size(); ++i) {
res = (res * C(n[i], k[i])) % MOD;
}Let’s talk about functionC(n[i], k[i])in more detail. It’s easy to see that(0 ≤ n[i], k[i] < MOD), so we can use formulaC(N, K) = N! / ((N – K)! * K!)and trick #3 fromthere:int C(int N, int K) {
if (K > N) {
return 0;
}
return (((fact[N] * binpow(fact[N – K], MOD – 2)) % MOD) * binpow(fact[K], MOD – 2)) % MOD;
}Let’s precalc all possible factorials moduloMODand store them in the arrayfact:long long fact[MOD];
fact[0] = 1;
for (int i = 1; i < MOD; ++i) {
fact[i] = (fact[i – 1] * i) % MOD;
}Functionbinpowis justFast exponentation, it can calculateAN% MODinO(log(N))time:int binpow(int a, int n) {
long long res = 1;
while (n > 0) {
if (n % 2 != 0) {
res = (res * a) % MOD;
}
a = ((long long)a * a) % MOD;
n /= 2;
}
return (int)res;
}Ifn[i]andk[i]are small enough instead of using formulas and tricks we can just precalcPascal’s triangleand then getC(n[i], k[i])inO(1):int C[MOD][MOD];
for (int i = 0; i < MOD; ++i) {
for (int j = 0; j <= i; ++j) {
if (i == 0 || j == 0) {
C[i][j] = 1;
} else {
C[i][j] = (C[i – 1][j – 1] + C[i – 1][j]) % MOD;
}
}
}Trick with not prime MOD:let’s factorizeMOD = mod1q1* mod2q2* … * modmqmand calculateC(N, K) % mod1, C(N, K) % mod2, … C(N, K) % modmusing Lucas’ Theorem. Now we can useChinese remainder theoremto restoreC(N, K) % MOD.Wilson’s TheoremStatement:Natural number N is a prime number if and only if (N – 1)! + 1 is divisible by N.

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *