这道题的核心是高效计算组合数 $C(n,k)$ 的因子个数。直接计算组合数再分解质因数会因数值过大而超时，因此采用基于素因子分解的预处理方法，具体思路如下：

关键思路：利用阶乘的素因子分解性质

组合数 $C(n,k) = \frac{n!}{k! \cdot (n-k)!}$，其素因子分解可通过各阶乘的素因子指数相减得到。而阶乘的素因子指数可通过 Legendre公式 快速计算：对于素数 $p$，$n!$ 中 $p$ 的指数为 $\left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots $（直到商为0）。

具体实现步骤

1. 预处理素数列表

使用埃拉托斯特尼筛法，找出435以内的所有素数（因题目中 $n \leq 431$，素数范围只需覆盖到435），存储于数组$f$中。

2. 预处理阶乘的素因子指数

对于每个素数 $p$（即 $f[i]$），预计算每个数 $j!$ 中 $p$ 的指数，存储于二维数组 $num[j][i]$（表示 $j!$ 中第 $i$ 个素数的指数）。
利用递推关系简化计算：
$ \text{num}[j][i] = \left\lfloor \frac{j}{f[i]} \right\rfloor + \text{num}\left[\left\lfloor \frac{j}{f[i]} \right\rfloor\right][i] $
（本质是Legendre公式的递归形式，避免重复计算每一层的商）

3. 预处理组合数的因子个数

组合数 $C(i,j)$ 的素因子指数为 $ \text{num}[i][k] - \text{num}[j][k] - \text{num}[i-j][k] $（$k$ 为素数索引）。将所有素因子的指数加1后相乘，即为 $C(i,j)$ 的因子个数，存储于二维数组 $C[i][j]$。

4. 处理输入输出

对于每个输入的 $n$ 和 $k$ 直接查表输出 $C[n][k]$。特殊情况（$k=0$ 或 $k=n$ 时$C(n,k)=1$, 因子个数为1）单独处理。

代码优势

• 预处理思想：通过预计算素数、阶乘的素因子指数、组合数的因子个数，将每次查询的时间复杂度降为 $O(1)$
• 避免大数计算：全程仅处理素因子指数，无需计算实际的组合数，规避了大数溢出问题。
• 高效性：预处理时间复杂度为 $O(P \cdot N \cdot \log N)$（$P$ 为素数个数，$N$ 为最大 $n$），查询时间为 $O(1)$，整体可在200ms内完成所有计算。

标程

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define mem(x,v) memset(x,v,sizeof(x))
using namespace std;
typedef long long LL;
int n,k,cnt = 0;
int f[500],num[500][500];
LL C[500][500];
bool vis[500];
void init(){
	mem(vis,1);
	vis[1] = 0;
	for (int i = 2; i <= 435; i++){
		if (vis[i]){
			f[cnt++] = i;
			for (int j = 2; i*j <= 435; j++)
				vis[i*j] = 0;
		}
	}
	mem(num,0);
	for (int i = 0; i < cnt; i++)
		for (int j = 1; j < 435; j++)  //num[i][j]表示i!中素因子prime[j]的个数。
			num[j][i] = j/f[i] + num[j/f[i]][i];
//预处理出C(i,j)的因子个数
	for (int i = 1; i < 450; i++)
		for (int j = 1; j < i; j++){
			C[i][j] = 1;
			for (int k = 0; k < cnt; k++){
				int d = num[i][k] -num[i-j][k] - num[j][k];
					C[i][j] *= (d+1);  //C[i][j](0<=j<=i)表示组合C(i,j)的因子个数。
			}
		}
	return;
}
 
int main(){
	init();
	while(scanf("%d%d",&n,&k) != EOF){
		if (n == k || k == 0) printf("1\n"); else
		printf("%I64d\n",C[n][k]);
	}
 
 
	return 0;
}