B3801 [NICA #1] 乘只因 题解
FFTotoro
·
·
题解
注意到题目中有一个很重要的性质：
\prod\limits_{i=1}^na_i=\mathrm{lcm}\{a_1,a_2,\ldots,a_n\}
易证 a_i 之间两两互质，即 \forall 1\le i<j\le n,\gcd(a_i,a_j)=1，所以如果 n 的唯一分解中包含的某个质数有多个，只能放在同一个 a_i 里。于是我们只需统计 n 的唯一分解中包含的质数种类数 c。
问题转化一下，就是如下的形式：
显然是第二类斯特林数，套递推公式直接计算即可。第二类斯特林数递推公式如下：
$$\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}$$
边界条件为 $\begin{Bmatrix}n\\0\end{Bmatrix}=[n=0]$。这里 $[]$ 指艾弗森括号。
放代码：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
bitset<10000001> b;
vector<int> p;
int f(int n,int m){
vector<vector<int> > s(n+1,vector<int>(m+1));
for(int i=0;i<=n;i++)s[i][0]=!i;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=s[i-1][j-1]+j*s[i-1][j];
return s[n][m];
} // 计算第二类斯特林数
main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for(int i=2;i<1e7;i++){
if(!b[i])p.emplace_back(i);
for(int j:p){
if(i*j>1e7)break;
b[i*j]=true;
if(!(i%j))break;
}
} // 线性筛
int t; cin>>t;
while(t--){
int n,k,c=0; cin>>n>>k;
for(int i:p){
if(i*i>n)break;
if(!(n%i))c++;
while(!(n%i))n/=i;
} // 统计质数种类数
if(n>1)c++;
if(k>c)cout<<"0\n"; // 特判
else cout<<f(c,k)<<'\n';
}
return 0;
}
```