fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MOD = 1000000007;
  4.  
  5. long long modpow(long long a, long long e){
  6.     long long r = 1;
  7.     while(e){
  8.         if(e&1) r = r*a % MOD;
  9.         a = a*a % MOD;
  10.         e >>= 1;
  11.     }
  12.     return r;
  13. }
  14.  
  15. int main(){
  16.     ios::sync_with_stdio(false);
  17.     cin.tie(nullptr);
  18.     int q; 
  19.     if(!(cin >> q)) return 0;
  20.     vector<pair<int,int>> qs(q);
  21.     int maxY = 0;
  22.     for(int i=0;i<q;i++){
  23.         int x,y; cin >> x >> y;
  24.         qs[i]={x,y};
  25.         maxY=max(maxY,y);
  26.     }
  27.     int N = 1000000;
  28.     vector<int> spf(N+1), primes;
  29.     for(int i=2;i<=N;i++){
  30.         if(!spf[i]){spf[i]=i; primes.push_back(i);}
  31.         for(int p:primes){
  32.             long long v=1LL*p*i;
  33.             if(v>N || p>spf[i]) break;
  34.             spf[v]=p;
  35.         }
  36.     }
  37.     int EXTRA = 25;
  38.     int M = maxY + EXTRA;
  39.     vector<long long> fac(M+1), invfac(M+1);
  40.     fac[0]=1;
  41.     for(int i=1;i<=M;i++) fac[i]=fac[i-1]*i%MOD;
  42.     auto modinv = [&](long long x){ return modpow(x, MOD-2); };
  43.     invfac[M]=modinv(fac[M]);
  44.     for(int i=M;i>=1;i--) invfac[i-1]=invfac[i]*i%MOD;
  45.     auto C = [&](int n,int r)->long long{
  46.         if(r<0 || r>n) return 0;
  47.         return fac[n]*invfac[r]%MOD*invfac[n-r]%MOD;
  48.     };
  49.  
  50.     for(auto [x,y]: qs){
  51.         long long ans = modpow(2, y-1);
  52.         int t = x;
  53.         while(t>1){
  54.             int p = spf[t], c = 0;
  55.             while(t%p==0){ t/=p; c++; }
  56.             ans = ans * C(c + y - 1, c) % MOD;
  57.         }
  58.         cout << ans % MOD << "\n";
  59.     }
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.01s 7748KB
comments (?)
stdin
copy 
2
6 3
4 2
stdout
copy 
36
6
https://ideone.com/BooB91
language:
C++14 (gcc 8.3)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!