题目：http://codeforces.com/contest/893/problem/E
题意：给出1e5组询问,每组要求y个整数乘积为x,输出组合种类数。(x,y<=1e6)
题解：把x分解成它的所有质因子乘积的形式，例如18=2*3*3 则可以把每个质因子分解为可空的y份，可利用组合数计算。假设有1个数字要分解为3份，可假设为1+3个数字分解为不可空的3份，转化为高中数学的隔板问题，cnt个数字分解为y份答案为$C^{y-1}_{cnt+y-1}$，分解的所有情况的乘积则为答案。先初始化1e6的素数表，分解每个数字，利用快速幂log计算组合数。
但是不能暴力对每一个数字寻找质因数，1e6*1e5肯定会T。需要做一些优化，先初始化出每个数字最小的质因子，然后从x开始向下转移，1e6的数字质因子数不超过20种，复杂度为O（q*20*logx）。
#include<bits/stdc++.h> #define pii pair<int, int> #define mod 1000000007 #define mp make_pair #define pi acos(-1) #define eps 0.00000001 #define mst(a,i) memset(a,i,sizeof(a)) #define all(n) n.begin(),n.end() #define lson(x) ((x<<1)) #define rson(x) ((x<<1)|1) #define inf 0x3f3f3f3f typedef long long ll; typedef unsigned long long ull; using namespace std; const int maxn = 1.5e6 + 500; vector<int>prime; int isprime[maxn]; void getprimelist(int t) { mst(isprime, 1); isprime[1] = 0; for (int i = 2; i <= t; ++i) { if (isprime[i])prime.push_back(i); for (int j = 0; j < prime.size() && prime[j] * i <= t; ++j) { isprime[prime[j] * i] = 0; if (i%prime[j] == 0)break; } } } ll quickmod(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans = ans*a%mod; b >>= 1; a = (a%mod)*(a%mod) % mod; } return ans; } ll c[maxn]; ll C(ll n, ll m) { return c[n] * quickmod(c[m] * c[n - m] % mod, mod - 2) % mod; } int init[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int i, j, k, m, n; getprimelist(1005000); c[0] = 1; c[1] = 1; for(int i= 2;i<=1005555;++i) c[i] = c[i - 1] * i%mod; int T; for(int i = 2;i<=1000000;++i) { if(isprime[i]) { init[i]=i; continue; } for(auto it :prime) { if(i%it==0) { init[i]=it; break; } } } cin >> T; while (T--) { cin >> n >> m; ll ans = 1; while(n>=2) { int cnt = 0; int now = init[n]; while (init[n]==now) { n /= now; cnt++; } ll tt = C(cnt + m - 1, m - 1); ans = ans*tt%mod; } ll tt = quickmod(2, m - 1); ans = tt*ans%mod; cout << ans << endl; } return 0; }