题解 | #祥子拆团#

我太菜了，只会做后两题

题目大意

给你一个数 ，求把它拆成 个整数乘积的方案数。

具体做法

1. 把 质因数分解
2. 枚举每一个质因数，把第 个因数的个数 拆成 个数的和共有 种方案，最后全部相乘。

注意事项

1. 在计算组合数的时候，不能直接用 这条公式，会超时。要优化成
2. 由于有模数，所以要求逆元

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1000000007;
int g[100010],len,ans,jc[100010];
int cj(int a){
    return jc[a];
}
int ksm(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}
int C(int n,int m){ //组合数
	int ans=1;
	for(int i=m+1;i<=n;i++) ans=ans*i%mod;
    return ans*ksm(cj(n-m),mod-2)%mod;
}
signed main(){
    jc[1]=jc[0]=1;
    int t;
    scanf("%lld",&t);
    for(int i=2;i<=100000;i++) jc[i]=jc[i-1]*i%mod;
    while(t--){
        int x,y;
        ans=1;
        len=0;
        scanf("%lld%lld",&x,&y);
        for(int i=2;i*i<=x;i++){
            if(x%i==0) len++,g[len]=0;
            while(x%i==0) g[len]++,x/=i;//质因数分解
        }
        if(x>1) g[++len]=1;
        for(int i=1;i<=len;i++) g[i]+=y-1,ans=(ans*C(g[i],y-1))%mod;
        printf("%lld\n",ans);
    }
    return 0;
}