fork download
copy 
  1. /*
  2.                                                                                                        
  3.                                                                                                        
  4.                                                                                                        
  5.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░   
  6.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░▒░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░   
  7.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▒▓▓▓▓▒▒░▒▒░░▒░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░   
  8.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒░░▒▒▒▒▒░▒▓▓██▓▓▓▓▓▓▓▓▓▓▒░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░   
  9.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▓▓▓▓█████▓▓███▓▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░   
  10.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒░░▒░▒▒▓▓▓████████▓▓▓▓▓▓▓▒░▒░░░░░▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░   
  11.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░░░▒▒▒▒▒▒▒▒▒▒▓▒▒▒▒▒▒▓▓█▓▓░░░░░░▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░░░   
  12.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░░▒▒▒▒▓▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▓▒░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░░░   
  13.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▓▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓▒▒▒▒▒▒▒▒░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░   
  14.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▓▓▓▒▒▒▒▒▒▒▒▒▒▓▓░░▒▒▒▒▒▒░░░▒▒▒▒▒░░▒▒▒▒▒▒▒░░░░░░░░░░░   
  15.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒░▒▒▓▓▓▒▓▓▓▒▒▓▓▓▒▒▒▒▓▒░░░░░▒▒▒▒▒▒▒▒▒▒▒░░░░▒▒▒▒▒▒▒▒▒░░░░░░░   
  16.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▓▒░▒▒▒▒▒▒▓▒▒▒▒▒▒▒▒▒▓▒░░░░░░░▒▒▒▒▒▒▒▒▒▒░░░░░▒▒▒▒▒▒▒▒░░░░░░░   
  17.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒░▒▒▒▒▓▓▓▓▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░▒▒▒▒▒▒▒▒░░░░▒▒▒▒▒░░░░▒▒▒▒░░   
  18.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒░▒▒▒▒▓▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░░▒▒▒▒▒▒▒▒░░░▒▒▒░░░░░░░▒▒▒▒▒▒   
  19.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▓▓▓▓▓▓▒▒▒▒▒▒▒░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░░▒▒▒▒   
  20.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▓▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒░░▒▒▒▒░░░░░░░▒▒▒▒   
  21.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▓▓▒▒▒▒▒▒▒▒▒░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒░░░░░▒▒░░░░░▒▒▒░░░   
  22.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒░░░░░░░░░▒▒▒▒▒▒▒▒▒▒▒░░░░░░░░▒░░░░░▒▒▒░░   
  23.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒░▒▓▓▓▓▒▒▒▒▒▒▒▒░▓▓▒░░░░░░░▒▒▒▒▒░▒▒▒▒▒▒░░░░░░░░░░░░░░░▒▒▒▒   
  24.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒░░░▒▒▒▓▓▓▓▒▒▒▒▒▒▒░▒▓███▓▒▒▒▒▒▒▒▒░░░▒▒▒▒▒▒▒░░░░░░▒░░░░░░░░▒▒▒   
  25.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒░▒▒▓▒▒▓▓▓▒▒▒▒▒░░░▓██████▓▓▓▓▓▓▒▒▒░▒▒▒▒▒▒▒░░░░░░▒░░░░░░░░▒▒▒   
  26.     ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▓▓▓▒▒▒░▒▒▒▒▒▒▓▓▓▒▒░░░▒████████████████▓▓▓▓▒▒▒▒░░░░░░▒░░░░░░░▒▒▒▒   
  27.     ░░░░░░░░░░░░░░░░░░▒▒▒░░░░░▒▒▒▓▓██▓█▓▒░▒▒▒▓▓▓▒▒▓▒▒░░░░▒▓██████████████████████▓▒░░░░░▒▒░░░░░░▒▒▒▒▒   
  28.     ░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▓▓▓▓███████▓▒░▒▒▒▓▓▓▒▒▒░░░░░▒██████████████████████████▒░░░░▒▒░░░░░▒▒▒░░░   
  29.     ░░▒░░░░░░░░░░░░░▒▒▒▒▒▒▓█████████████▓██▒▒▓▓▓▒▒▓▓▒░░▒███████████████████████████▓░▒▒▒▒▒░░░░▒▒▒▒░░░   
  30.     ░▒░▒░░░░░░░░░░░░░░▒▒▒▒▓████████████████▓▓▓▓▓▒▒▓▒▒▒▒▒████████████████████████████▒░░░▒▒▒▒░▒▒▒░░░░░   
  31.     ▒▒▒▒▒▒▒░░░░░░░░░░░░░▒▒▓████████████████▓▓▓▓▒▒▓▒▒▒▒▒██████████████████████████████▒░░░░▒▒▒▒▒▒▒▒▒▒░   
  32.     ▒▒▒▒▒▒▒░░░░░░░░░░░░▒▒▒▓██████████████████▒▒▒▓▒▒▒▒▒▓██████████████████████████████▒░░░░░▒▒▒▒▒▒▒▒▒▒   
  33.     ▒▒▒▒▒▒▒▒░░░░░░░▒▒▒▒▒▒▒▓████████████████▓▓▒▒▒▒▒▒▒▒▓███████████████████████████████▓░░░░▒▒▒▒▒▒▒░░░░   
  34.     ▒▒░░▒▒▒▒▒░░░░░░▒▒▒▒▒▒▒▓████████████████▓▒▒▒▒▒▒▒▒▓█████████████████████████████████▓░░░▒▒▒▒▒▒▒▒░░░   
  35.     ▒▒░░░▒▒▒▒▒░░░░░░▒▒▒▒▒▒████████████████▓▒▒▒▒▒▒▒▓▓███████████████████████████████████▒░░░▒▒▒░▒▒▒░░░   
  36.     ▒░░░░░▒░░░░░░░░░░░▒▒▒▓█████████████████▒▒▒▒▒▓████████████████████████████████████████▓▓▒▒░░░▒░░░░   
  37.     ▒░░░░░▒░░░░░░░░░░▒▒▒▒▓█████████████████▓▓▓▓▓████████████▒▒▒▒▒▒▒▒▓▓██████████████████████▓░░░░░░░░   
  38.     ░░░░░▒▒▒░░░░░░░░░▒░▒▒▓████████████████████▓▓█▓▓▓████████▒▓▓▓▓▓▓▒▒▒▓████████████████████████▓░░░░░   
  39.     ░░░▒▒▒▒░░░░░░░░▒▒▒▒▒▒▒████████████████████▓▓▓▓▒▓████████▓▓▓▓▓▓▓▓▒▒▒▒▓████████████████████████▒▒▒░   
  40.     ░░▒▒▒▒▒▒░░░░░░░▒▒▒▒▒▒▒█████████████████▓▓▒▓▓▒▒▒▓█████████▓▓▓▓▒▒▒▒▒▒▒▒████████████████████████▓░▒▒   
  41.     ▒▒▒▒▒░░░░▒▒░░░░░▒▒▒▒▒▒█████████████████▓▒▒▓▓▒▓▓███████████▓▓▓▒▒▒▒▒▒▒▒▓███████████████████████▓░▒▒   
  42.     ▒▒░░░░░░░░░░░░░░░▒▒▒▒▒▓████████████████▓▓▒▓▓▓▓▓████████████████▓▓▓▒▒▒▓███████████████████████▓░▒▒   
  43.     ▒▒░░░░░░░░░░░░░░▒▒▒▒▒▓█████████████████▓▓▓▓▓██████████████████████▓▓▓▓▓███████████████████████▒▒▒   
  44.     ░░░░░░░░░░░░░▒▒▒▒▒▒▒▒▓▓▓▓▓███▓▓▒▒▒▒▓▓▓▓██▓▓████████████████████████████████▒▓▒████████████████▒▒▒   
  45.     ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓███▓▒▒▒▓▓▓▓▓▓▓█████▓██▓███████████████████████████████████████████████▒▒▒▒   
  46.     ▒░░░░░░░░░░░░▒▒▒▒▒▒▒▒▒▓██▓▓▓▓▒▓▓▓▓▓▓▓▓███▓▓▓▓▓████████████████████████████████████████████▓▒▒▒▒▒▒   
  47.     ▒▒▒▒░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▓█▓███▓▓▓▓▓▓▓▓▓▓███▓▓▓▓▓█████████████████████████████▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒   
  48.     ▒▒▒░▒░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓█████▓▓▓▓▓▓▓▓████▓▓▓▓▓██████████████████████████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒   
  49.     ▒▒▒▒░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓██▓▓▓▓▓▓█████▓▓▓▓███████████████████████████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒   
  50.     ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓█████████████▓█████████████████████████████████▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒   
  51.     ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓████████▓█████████████████████████████████▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒   
  52.     ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓█████▓▓▓▓▓██████████████████████████████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒   
  53.     ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓█████▓▓▓▓▓▓█████████████████████████████████▓▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒   
  54.     ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▓▓█████▓▓▓▓▓▓██████████████████████████████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒   
  55.                                                                                                        
  56.                                                                                                        
  57.  
  58. */
  59.  
  60. #include <bits/stdc++.h>
  61. #define ll long long
  62. #define fi first
  63. #define se second
  64. #define pa pair<ll,int>
  65. using namespace std;
  66.  
  67. const ll mod = 1e9 + 19972207;
  68. const ll maxN = 220797 + 36;
  69. const ll inf = 4e18;
  70.  
  71. ll t, n, k;
  72. vector<ll> vec;
  73.  
  74. ll mul(ll a, ll b)
  75. {
  76.     ll res = 0;
  77.     a %= mod; b %= mod;
  78.     while (b > 0)
  79.     {
  80.         if (b & 1) res = (res + a) % mod;
  81.         a = (a + a) % mod;
  82.         b >>= 1;
  83.     }
  84.     return res;
  85. }
  86. ll bpow(ll num, ll exp)
  87. {
  88.     ll res = 1;
  89.     while (exp)
  90.     {
  91.         if (exp & 1) res = mul(res, num);
  92.         num = mul(num, num);
  93.         exp >>= 1;
  94.     }
  95.     return res;
  96. }
  97. ll inv(ll x) {return bpow(x, mod - 2);}
  98. int main()
  99. {
  100.     freopen("divseq.inp", "r", stdin);
  101.     freopen("divseq.out", "w", stdout);
  102.     ios_base::sync_with_stdio(0);
  103.     cin.tie(0); cout.tie(0);
  104.     cin >> n >> k;
  105.     for (ll p = 2; p * p <= n; p++)
  106.         if (n % p == 0)
  107.         {
  108.             ll cnt = 0;
  109.             while (n % p == 0)
  110.             {
  111.                 n /= p;
  112.                 cnt++;
  113.             }
  114.             vec.push_back(cnt);
  115.         }
  116.     if (n > 1) vec.push_back(1);
  117.  
  118.     ll ans = 1;
  119.     for (ll e : vec)
  120.     {
  121.         ll num = 1, den = 1;
  122.         for (ll i = 0; i < e; i++) num = mul(num, (k + i) % mod);
  123.         for (ll i = 1; i <= e; i++) den = mul(den, i);
  124.         ans = mul(ans, mul(num, inv(den)));
  125.     }
  126.  
  127.     cout << ans << "\n";
  128.     return 0;
  129. }
  130.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YwGBj0
language:
C++ (gcc 8.3)
created:
4 hours 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!