思路:把相同的质因子看成相同的小球,求把这些小球放进n个盒子里的方案数。
代码:
#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#includeusing namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL unsigned long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair #define pii pair #define piii pair #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 2e5 + 10;const int MOD = 1e9 + 7;int fac[N], inv[N];int cnt[N];LL q_pow(LL n, LL k) { LL ans = 1; while(k) { if(k&1) ans = (ans * n) % MOD; n = (n * n) % MOD; k >>= 1; } return ans;}void init() { fac[0] = 1; for (int i = 1; i < N; i++) { fac[i] = (1LL * fac[i-1] * i) % MOD; } inv[N-1] = q_pow(fac[N-1], MOD-2) % MOD; for (int i = N-2; i >= 0; i--) inv[i] = (1LL * inv[i+1] * (i+1)) % MOD;}LL C(int n, int m) { return ((1LL * fac[n] * inv[m]) % MOD * inv[n-m]) % MOD;}int main() { int n, m, up = 0; init(); scanf("%d %d", &n, &m); for (int i = 2; i*i <= m; i++) { if(m % i == 0) { int tmp = 0; while(m % i == 0) m /= i, tmp++; cnt[++up] = tmp; } } if(m > 1) cnt[++up] = 1; LL ans = 1; for (int i = 1; i <= up; i++) ans = (ans * C(cnt[i]+n-1, n-1)) % MOD; printf("%lld\n", ans); return 0;}