fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define sl(n) scanf("%lld", &n)
  6. #define pll pair <ll, ll>
  7. #define ms(n, i) memset(n, i, sizeof(n))
  8. #define pf printf
  9.  
  10. const ll mod = 10000007;
  11.  
  12. #define x first
  13. #define y second
  14. pll extendedEuclid(ll a, ll b)
  15. {
  16.     if(b == 0) return pll(1, 0);
  17.     else
  18.     {
  19.         pll d = extendedEuclid(b, a % b);
  20.         return pll(d.y, d.x - d.y * (a / b));
  21.     }
  22. }
  23.  
  24. ll modularInverse(ll a, ll n)
  25. {
  26.     pll ret = extendedEuclid(a, n);
  27.     return ((ret.x % n) + n) % n;
  28. }
  29.  
  30. ll fastPow(ll x, ll n)
  31. {
  32.     ll ret = 1;
  33.     while (n)
  34.     {
  35.         if (n & 1) ret = (ret * x) % mod;
  36.         x = (x*x) % mod;
  37.         n >>= 1;
  38.     }
  39.     return ret % mod;
  40. }
  41.  
  42. ll sumGeo(ll a, ll r, ll n)
  43. {
  44.     ll den = modularInverse(r-1, mod);
  45.  
  46.     ll nom = fastPow(r, n) - 1;
  47.     if(nom < 0) nom += mod;
  48.  
  49.     nom = (a * nom) % mod;
  50.     return (nom * den) % mod;
  51. }
  52.  
  53. ll cnt[10];
  54.  
  55. int main()
  56. {
  57.     ll t, n, x;
  58.     cin >> t;
  59.  
  60.     while(t--) {
  61.         sl(n), sl(x);
  62.  
  63.         assert(1 <= x && x <= (ll)1e17);
  64.  
  65.         for(ll i = 2; i <= n; i++) {
  66.             while(n % i == 0) {
  67.                 cnt[i]++;
  68.                 n /= i;
  69.             }
  70.         }
  71.  
  72.         cnt[2] += x, cnt[5] += x;
  73.         ll ans = 1;
  74.  
  75.         for(ll i = 2; i <= 9; i++) {
  76.             if(i == 2) ans = (ans * sumGeo(2, 2, cnt[2])) % mod;
  77.             else     ans = (ans * sumGeo(1, i, cnt[i] + 1)) % mod;
  78.         }
  79.  
  80.         pf("%lld\n", ans);
  81.  
  82.         ms(cnt, 0);
  83.     }
  84.  
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0s 4472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6290777
https://ideone.com/xv2UfV
language:
C++14 (gcc 8.3)
created:
3 years 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!