当前位置：首页 > news >正文

数论：卢卡斯定理

news 2025/8/3 10:12:25

卢卡斯定理用于计算组合数 C(n,k) mod p，其中 p 是一个质数。它将大组合数的模运算分解为多个小组合数的模运算的乘积，从而简化计算。

求组合数的办法又很多种，今天带来主要的三种求组合数的方式，分别对应不同的情况以及数据范围，并整理出相关模板，大家可以根据在竞赛中的实际情况来选择合适的求组合数的方式。

递推关系求组合数

众所周知，组合数C(n,k)是从n个物品中选择k个物品的组合数，当我们取出一个物品时，我们可以将所有情况分为两类，第一类是k中包含这个物品，第二类是k中不包含这个物品，而第一种情况就相当于是从剩下的n-1个物品中选择k-1个物品，即C(n-1,k-1)，第二种情况就相当于是从n-1个物品中选择k个物品，即C(n-1,k)，所以就有了如下的递推式：

$C(n,k) = C(n-1,k) + C(n-1,k-1);$

所以就有了以下代码：

int res[N][N];
void init()
{for(int i=0;i<N;i++){for(int j=0;j<=i;j++){if(!j || j == i) res[i][j] = 1;else res[i][j] = (res[i-1][j-1] % mod + res[i-1][j] % mod) % mod;}}
}

这个代码可以准确地处理时间复杂度在O(N²)时计算组合数的情况，一般在算法竞赛中较少出现，下面给大家带来O(N)的时间复杂度的计算组合数的方法，是通过乘法逆元 + 费马小定理来实现的。

阶乘 + 逆元求组合数

众所又周知，C(n,k)可以通过阶乘来计算，即C(n,k) = n! / (k! * (n - k)!)，乘法是遵循同余性质的，而除法就需要用到乘法逆元来处理了，但是要求mod必须是质数，具体模板如下：

int jc[N];//阶乘数组
int ny[N];//逆元数组
int ksm(int a,int b)
{int ans=1;while(b){if(b&1) ans = (ans * a) % mod;a = (a * a) % mod;b >>= 1;}return ans%mod;
}
void init()
{jc[0] = 1;for(int i=1;i<=n;i++) jc[i] = jc[i-1] % mod * i % mod;ny[n] = ksm(jc[n],mod-2);for(int i=n-1;i>=0;i--) ny[i] = (ny[i+1] * (i+1)) % mod;//查询C(n,k):int C = ((jc[n] * ny[k]) % mod * ny[n-k]) % mod;
}

卢卡斯定理求组合数

当数据范围过大的时候，比如n和k来到了1e18的时候，上面的两种方法就不再适用了，这时候如果mod的范围又不大，就可以考虑用卢卡斯定理来求组合数了，具体的卢卡斯定理的公式为：

C(n,k) % mod = C(n % mod, k % mod) * C(n / mod, k / mod);

具体的模版代码如下：

int ksm(int a,int b)
{int ans=1;while(b){if(b&1) ans = (ans * a) % mod;a = (a * a) % mod;b >>= 1;}return ans%mod;
}
void init()
{jc[0] = 1;for(int i=1;i<=n;i++) jc[i] = jc[i-1] % mod * i % mod;ny[n] = ksm(jc[n],mod-2);for(int i=n-1;i>=0;i--) ny[i] = (ny[i+1] * (i+1)) % mod;
}
int C(int n,int k)
{if(k < 0 || k > n) return 0;return ((jc[n] * ny[k]) % mod * ny[n-k]) % mod;
}
int lucas(int n,int k)
{if(n < mod && k < mod) return C(n,k);return C(n % mod,k % mod) * lucas(n / mod,k / mod) % mod;
}

一些常用的数论模板整理如下，有需要的小伙伴可以收藏起来：

常用数论模板

判断是否为素数

bool is_prime(int x)
{if (x < 2) return false;for (int i = 2; i * i <= x; i++)if (x % i == 0) return false;return true;
}

分解质因数

void divide(int x)
{for (int i = 2; i <= x / i; i ++ )if (x % i == 0){int s = 0;while (x % i == 0) x /= i, s ++ ;cout << i << ' ' << s << endl;}if (x > 1) cout << x << ' ' << 1 << endl;cout << endl;
}

埃氏筛筛素数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (st[i]) continue;primes[cnt ++ ] = i;for (int j = i + i; j <= n; j += i)st[j] = true;}
}

欧拉筛筛素数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i;for (int j = 0; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}

求所有约数

vector<int> get_divisors(int x)
{vector<int> res;for (int i = 1; i <= x / i; i ++ )if (x % i == 0){res.push_back(i);if (i != x / i) res.push_back(x / i);}sort(res.begin(), res.end());return res;
}

扩展欧几里得算法模板

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{if (!b){x = 1; y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= (a/b) * x;return d;
}

整除分块

void solve()//求约数个数之和
{cin>>n;int ans=0;int l=1,r=1,k;for(int i=1;i<=n;i++)//枚举所有的因子{k = n/i;//从1到n里面有几个i的倍数r = n/k;//通过整除分块来确定右边界ans += k*(r-l+1);//这个区间内的所有因子在1到n中都有k个该因子的倍数（即他们都作为k个数的因子）l = r+1;//更新完答案之后更新左边界i = r;//直接跳过这段区间 省去大量时间！}cout<<ans<<endl;
}

详解请看这篇博客：整除分块