赛时 5 分钟打完，zjy 打正解用了 0.5h。

首先想到质因数分解，得到一堆分开的质因数。

然后题目即求对于每一个质因数，将它分在 $N$ 个数的方法数的乘积。

这个东西需要找规律然后用组合数，但我不想动脑子去算，所以……

直接暴力 dp 求解！！！

时间复杂度 $O(N\log(M)^2)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,P=1e9+7;
int dp[N][40];int n,m;
bool v[N];int p[N],pr;
void init()
{
	pr=0;memset(v,0,sizeof(v));
	for(int i=2;i<=N-10;i++)
	{
		if(!v[i])p[++pr]=i;
		for(int j=1;(j<=pr)&&(i*p[j]<=N-10);j++)
		{
			v[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
}
signed main()
{
	init();
	cin>>n>>m;int ans=1;
	dp[0][0]=1;
	for(int i=0;i<=n;i++)for(int j=0;j<=31;j++)for(int k=0;j+k<=31;k++)
		dp[i+1][j+k]=(dp[i+1][j+k]+dp[i][j])%P;
	for(int i=1;i<=pr;i++)
	{
		int sum=0;
		while(m%p[i]==0)m/=p[i],sum++;
		ans=ans*dp[n][sum]%P;
		if(m==1)break;
	}
	if(m!=1)ans=ans*n%P;
	cout<<ans;
	return 0;
}

学校模拟赛时找规律过了，写篇题解纪念一下。

怎么找规律呢？先 dfs 打出 $N\leq5,M\leq24$ 的表。

void dfs(int k,int sum)
{
	if(k>n)
	{
		if(sum==m) ans++;
		return;
	}
	if(sum>m) return;
	for(int i=1;i<=m;i++) dfs(k+1,sum*i);
}

 M=1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24
   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
   1   2   2   3   2   4   2   4   3   4   2   6   2   4   4   5   2   6   2   6   4   4   2   8
   1   3   3   6   3   9   3  10   6   9   3  18   3   9   9  15   3  18   3  18   9   9   3  30
   1   4   4  10   4  16   4  20  10  16   4  40   4  16  16  35   4  40   4  40  16  16   4  80
   1   5   5  15   5  25   5  35  15  25   5  75   5  25  25  70   5  75   5  75  25  25   5 175

根据表，首先得到一个结论：答案与 $M$ 究竟是多少无关，只与 $M$ 的质因数的次数有关。如 $M=12=2^2\times3$ 和 $M=18=3^2\times2$ 这两列是一样的。

找出质因数构成不同的那些数，取 $2,4,6,8,12$，设答案为 $ans$，找出这些列的规律（下面的 $p_1,p_2$ 表示两个质数，且 $p_1\neq p_2$）：

$M=2$ 时，即 $M=p_1$ 时，$ans=N$。

$M=4$ 时，即 $M=p_1^2$ 时，$ans=C_{N+1}^2$。

$M=6$ 时，即 $M=p_1\times p_2$ 时，$ans=N^2$。

$M=8$ 时，即 $M=p_1^3$ 时，$ans=C_{N+2}^3$。

$M=12$ 时，即 $M=p_1^2\times p_2$ 时，$ans=C_{N+1}^2\times N$。

综上，可以找到规律：把 $M$ 分解质因数，$M=p_1^{a_1}\times p_2^{a_2}\dots\times p_k^{a_k}$。则 $ans=\prod\limits_{i=1}^kC_{N+a_i-1}^{a_i}$。用逆元求解即可。

其实这道题数学推理一点都不难，但是我太菜了没推出来。用插板法也可以推出 $ans=\prod\limits_{i=1}^kC_{N+a_i-1}^{a_i}$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,INF=0x3f3f3f3f,Mod=1e9+7;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void Write(int x){if(x<0){putchar('-'),Write(-x);return;}if(x<10){putchar(x+'0');return;}Write(x/10),putchar(x%10+'0');}
void write(int x,char *s){Write(x),printf("%s",s);}
int n,m,len,ans=1,fac[N],ifac[N],pr[N],cnt[N];
int power(int a,int b=Mod-2) {int ans=1;while(b) {b&1?ans=ans*a%Mod:1,b>>=1,a=a*a%Mod;}return ans;}
int C(int n,int m) {return n>=m?fac[n]*ifac[m]%Mod*ifac[n-m]%Mod:0;}
void solve()
{
	n=read(),m=read(),fac[0]=1;
	for(int i=1;i<=N-10;i++) fac[i]=fac[i-1]*i%Mod;
	ifac[N-10]=power(fac[N-10]);
	for(int i=N-11;~i;i--) ifac[i]=ifac[i+1]*(i+1)%Mod;
	for(int i=2;i*i<=m;i++)
		if(m%i==0)
		{
			pr[++len]=i;
			while(m%i==0) cnt[len]++,m/=i;
		}
	if(m!=1) pr[++len]=m,cnt[len]=1;
	for(int i=1;i<=len;i++) ans=ans*C(n+cnt[i]-1,cnt[i])%Mod;
	write(ans,"");
}
signed main()
{
	int T=1;
	while(T--) solve();
}