题解 | #祥子拆团#

这里主要写写独立性的感性理解证明，方便理解：

让我们来看一个例子(当x=216,y=2时)

    216分解后为：2*2*2*3*3*3
    独立性证明：
        2 | 2 2 
    3 3 3 |
      3 3 | 3
          | 3 3 3
        3 | 3 3
    如上所示为一个2的方案 可以与3的所有独立方案都形成新的组合依次类推 
    原因是因为2和3是不同的数字且互质，所以不会出现重复的情况
    综上故满足独立性

AC代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
#define x first
#define y second
#define de(a)  #a << " = " << (a) 
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int,int> PII;
constexpr int N=2e5+10,mod=1e9+7,inf=0x3f3f3f3f3f3f3f3f;
constexpr double eps=1e-8,pi=acos(-1.0);
int qmi(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
int c(int a,int b)
{
	if(b>a)return 0;
	int sum=1;
	for(;b>=1;b--,a--)
	{
	    sum=sum*a%mod;
		sum=sum*qmi(b,mod-2)%mod;
	}
	return sum;
}
int lucas(int a,int b)
{
	if(b==0)return 1;
	return lucas(a/mod,b/mod)*c(a%mod,b%mod)%mod;
}
void solve(int T)
{
    int x,y,sum=0;
    cin>>x>>y;
    map<int,int>h;
	auto qfn=[&](int x,map<int,int>&t){
		for(int i=2;i<=x/i;i++)while(x%i==0)x/=i,t[i]++;
		if(x>1)t[x]++;
	};
    qfn(x,h);
    int ans=1;
    for(auto i:h)ans=ans*lucas(y+i.y-1,i.y)%mod;
    cout<<ans<<endl;
}
signed main()
{
    bool multitest=1;
    //cout<<setiosflags(ios::fixed),cout.precision(2);
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int _t=1;
    if(multitest)cin>>_t;
    for(int i=1;i<=_t;i++)
    {
        solve(i);
    }
    return 0;
}