fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. const int MOD = 998244353;
  6.  
  7. ll powmod(ll a, ll b) {
  8.     ll res = 1;
  9.     a %= MOD;
  10.     while (b) {
  11.         if (b & 1) res = res * a % MOD;
  12.         a = a * a % MOD;
  13.         b >>= 1;
  14.     }
  15.     return res;
  16. }
  17.  
  18. ll cntdivi(ll n) {
  19.     ll cnt = 1;
  20.     for (ll i = 2; i * i <= n; ++i) {
  21.         if (n % i != 0) continue;
  22.         ll e = 0;
  23.         while (n % i == 0) {
  24.             n /= i;
  25.             ++e;
  26.         }
  27.         cnt *= (e + 1);
  28.     }
  29.     if (n > 1) cnt *= 2;
  30.     return cnt;
  31. }
  32.  
  33. int main() {
  34.     ios::sync_with_stdio(false);
  35.     cin.tie(nullptr);
  36.     int T;
  37.     cin >> T;
  38.     while (T--) {
  39.         ll n;
  40.         cin >> n;
  41.         ll tmp = cntdivi(n);
  42.         ll res = powmod(n, tmp / 2);
  43.         if (tmp % 2 == 1) {
  44.             ll sq = (ll)sqrt(n);
  45.             if (sq * sq != n) {
  46.                 cout << "Never gonna give you up!\n";
  47.                 exit(0);
  48.             }
  49.             res = res * sq % MOD;
  50.         }
  51.         cout << res << '\n';
  52.     }
  53. }
  54.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/a4XKFt
language:
C++14 (gcc 8.3)
created:
1 day 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!