Hint1

题目中所给函数对于求组合数的因子个数是否有用？

Hint2

直接求解因子个数显然不行,能不能间接从其他点切入？

Solution

本题考察 判断质数、筛质数、唯一分解定理、阶乘质因数分解

首先题目给出了复杂度 $O(\sqrt{n})$ 求一个数的因子个数的函数,但是对于本题没有任何帮助,组合数大小为阶乘级别,且需要高精度存储,该方法完全行不通。

既然无法直接正向求解,不妨把切入点指向间接求解,因子个数除了正向求解的方法外,还有数论中唯一分解定理可以间接求解,下面对其进行介绍

唯一分解定理（又称算术基本定理）指出：每个大于1的整数都可以表示为质数的乘积，并且这种表示在忽略因子的顺序时是唯一的。

例如:

1. $9=3^2$
2. $15=3×5$
3. $100=2^2×5^2$

根据唯一分解定理，若整数 $$ n $$ 的质因数分解为( $p_i$ 是质数)：

​ $n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$

则 $$ n $$ 的因子（约数）总数为：

​ $(a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$

例如:

1. $9=3^2$ 因子个数 $(2+1)=3$
2. $15=3×5$ 因子个数 $(1+1) \times (1+1)=4$
3. $100=2^2×5^2$ 因子个数 $(2+1) \times (2+1)=9$

至于此,我们已经换了另一种求解因子个数的算法,但我们还需要把组合数转化为质因数分解,这样才能求得因子个数

$C(n,m)$=$\frac{n!}{m!(n-m)!}$ 要想把组合数转化为质因数分解,我们先得对阶乘进行质因数分解

快速阶乘质因数分解过程如下:

$n!=\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+\cdots+\frac{n}{p^\infty}$

例如 $4!$ 中质因子 $2$ 出现了多少次？ 根据验算 $4 \times 3 \times 2 \times 1=2^3 \times 3$ 我们知道 $2$ 出现了 $3$ 次,根据我们算法来进行计算 $4!=\frac{4}{2}+\frac{4}{4}+0=3$

至此,我们已经可以进行阶乘质因数分解,如果我们能转化为组合数质因子分解,就可以根据唯一分解定理结论求得因子个数,观察式子 $C(n,m)$=$\frac{n!}{m!(n-m)!}$ 我们发现其实都是阶乘,对于其中的三个阶乘我们都可以进行阶乘质因数分解,而最后的组合数的质因数分解其实就是把分子的各个质因数个数减去分母的质因数个数,会出现分子有的某个质因数个数对应的分母没有吗？或分子有的某个质因数个数比对应的分母的少吗？ 不会的,根据常识组合数最终结果都是整数,所以就可以安心的计算啦！

总结一下关键过程, 先对组合数公式中三个阶乘进行阶乘质因数分解,然后把三个阶乘质因数分解组合为组合数质因数分解,最后就可以用唯一分解定理中的求解因子个数的公式进行计算,同时注意取模。

整个过程分为了几个部分进行计算,所有部分的时间复杂度最大也不会超过 $O(t \times log(n))$ , 其中 $t$ 为 $1$ 到 $max(n,m)$ 中的数满足是质数的个数,明显不会超过 $max(n,m)$ , $log(n)$ 为阶乘质因数分解的时间复杂度, 即时间复杂度最大也才 $max(n,m) \times log(n)$

C++代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int mod = 1e9 + 7;
int prime[1000010], idx, st[1000010];
void get_primes(int n) {//欧拉筛质数模版
	for (int i = 2; i <= n; i++) {
		if (!st[i])
			prime[idx++] = i;
		for (int j = 0; prime[j] <= n / i; j++) {
			st[prime[j] * i] = 1;
			if (i % prime[j] == 0)
				break;
		}
	}
}
void solve() {
	int n, m;
	cin >> n >> m;
	get_primes(max(n, m));//欧拉筛质数,复杂度O(n)
	vector<int> cnt(n + 10);//存质因数分解的状态
	//函数:求x的阶乘中,所有质因子出现了多少次 f为1代表加上次数 f为-1代表减去次数
	auto get = [&](int x, int f) {
		for (int i = 0; i < idx; i++) {
			int t = x, p = prime[i];
			if (p > x)
				break;
			while (t / p >= 1) {
				cnt[p] += f * t / p;
				t /= p;
			}
		}
	};
	get(n, 1), get(m, -1), get(n - m, -1);//到目前为止cnt已经存储的是组合数的质因数分解
	int ans = 1;
	for (int i = 2; i <= n; i++) {//唯一分解定理求因子个数公式
		ans = ans * (cnt[i] + 1) % mod;
	}
	cout << ans << endl;
}
signed main() {
	int t = 1;
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	//	cin>>t;
	while (t--) solve();
	return 0;
}