fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define debug     cout << "ok\n";
  4. #define SQR(x)    (1LL * ((x) * (x)))
  5. #define MASK(i)   (1LL << (i))
  6. #define BIT(x, i) (((x) >> (i)) & 1)
  7. #define fi        first
  8. #define se        second
  9. #define pb        push_back
  10.  
  11. #define mp make_pair
  12. #define pii pair<int,int>
  13. #define pli pair<ll,int>
  14. #define vi vector<int>
  15.  
  16. #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  17.  
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef long double ld;
  21. typedef unsigned int ui;
  22.  
  23. using namespace std;
  24.  
  25. const int M = 998244353;
  26. const int INF = 1e9 + 7;
  27. const ll INFLL = (ll)2e18 + 7LL;
  28. const ld PI = acos(-1);
  29.  
  30. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  31. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  32.  
  33. template<class _, class __>
  34.     bool minimize(_ &x, const __ y){
  35.         if(x > y){
  36.             x = y;
  37.             return true;
  38.         } else return false;
  39.     }
  40. template<class _, class __>
  41.     bool maximize(_ &x, const __ y){
  42.         if(x < y){
  43.             x = y;
  44.             return true;
  45.         } else return false;
  46.     }
  47.  
  48. template<class _,class __>
  49.     void Add(_ &x, const __ y) {
  50.         x += y;
  51.         if (x >= M) {
  52.             x -= M;
  53.         }
  54.         return;
  55.     }
  56.  
  57. template<class _,class __>
  58.     void Diff(_ &x, const __ y) {
  59.         x -= y;
  60.         if (x < 0) {
  61.             x += M;
  62.         }
  63.         return;
  64.     }
  65.  
  66. //--------------------------------------------------------------
  67.  
  68. int n,k;
  69. vector<pii> a;
  70.  
  71. int mul(int a,int b) {
  72.     return 1LL*a*b%M;
  73. }
  74.  
  75. int FP(int base,int n) {
  76.     if (n == 0) return 1;
  77.     if (n == 1) return base;
  78.     int tmp = FP(base,n/2);
  79.     tmp = mul(tmp,tmp);
  80.     if (n&1) tmp = mul(tmp,base);
  81.     return tmp;
  82. }
  83.  
  84. int Div(int a,int b) {
  85.     return mul(a,FP(b,M-2));
  86. }
  87.  
  88. int diff(int a,int b) {
  89.     a -= b;
  90.     if (a < 0) a += M;
  91.     return a;
  92. }
  93.  
  94. int Get(pii x) {
  95.     int l = x.se;
  96.     int a = x.fi;
  97.     int r = mul(FP(2,k),x.se);
  98.     int tmp = (r - l + 1 + M)%M;
  99.     int res = FP(a,l);
  100.     res = mul(res,diff(FP(a,tmp),1));
  101.     res = Div(res,diff(a,1));
  102.     return res;
  103. }
  104.  
  105. void sol() {
  106.     cin >> n >> k;
  107.     if (n == 1) {
  108.         cout << 1;
  109.         return;
  110.     }
  111.     for (int i=2;1LL*i*i<=n;i++) {
  112.         if (n % i == 0) {
  113.             int tmp = 0;
  114.             while(n%i == 0) {
  115.                 tmp++;
  116.                 n /= i;
  117.             }
  118.             a.pb(mp(i,tmp));
  119.         }
  120.     }
  121.     if (n > 1) a.pb(mp(n,1));
  122.     int res = 1;
  123.     for (pii x : a) {
  124.         res = Get(x);
  125.     }
  126.     cout << res;
  127. }
  128.  
  129. int main() {
  130. 	freopen("DIV.inp","r",stdin);
  131. 	freopen("DIV.out","w",stdout);
  132. 	FAST
  133. 	int t=1;
  134. //	cin >> t;
  135. 	while (t--) sol();
  136. }
  137.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/uwP51F
language:
C++14 (gcc 8.3)
created:
7 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!