fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fast ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
  4. #define pb push_back
  5. #define ll long long
  6. #define ull unsigned long long
  7. using u64 = uint64_t;
  8. using u128 = __uint128_t;
  9. u64 bp(u64 b, u64 e, u64 m) {
  10.     u64 r = 1;
  11.     b %= m;
  12.     while (e) {
  13.         if (e & 1) r = (u128)r * b % m;
  14.         b = (u128)b * b % m;
  15.         e >>= 1;
  16.     }
  17.     return r;
  18. }
  19. bool ck(u64 n, u64 a, u64 d, int s) {
  20.     u64 x = bp(a, d, n);
  21.     if (x == 1 || x == n - 1) return false;
  22.     for (int i = 1; i < s; i++) {
  23.         x = (u128)x * x % n;
  24.         if (x == n - 1) return false;
  25.     }
  26.     return true;
  27. }
  28.  
  29. bool isP(u64 n) {
  30.     if (n < 2) return false;
  31.     int r = 0;
  32.     u64 d = n - 1;
  33.     while ((d & 1) == 0) d >>= 1, r++;
  34.     for (int a : {2,3,5,7,11,13,17,19,23,29,31})
  35.         if (n % a == 0) return false;
  36.     for (int a : {2,3,5,7,11,13,17,19,23,29,31})
  37.         if (ck(n, a, d, r)) return false;
  38.     return true;
  39. }
  40. const int N = 4e6;
  41. int p[N];
  42. vector<int> pr;
  43. map<ull, int> mp;
  44. void gen() {
  45.     for (int i = 2; i < N; i++) {
  46.         if (!p[i]) {
  47.             for (int j = i + i; j < N; j += i) p[j] = i;
  48.             pr.pb(i);
  49.         }
  50.     }
  51.     ull lim = 1e9; lim *= lim * 10;
  52.     for (int i = 0; i < (int)pr.size(); i++) {
  53.         ull mul = 1;
  54.         for (int j = i; j < (int)pr.size(); j++) {
  55.             if (mul <= lim / pr[j]) {
  56.                 mul *= pr[j];
  57.                 mp[mul] = 1;
  58.             } else break;
  59.         }
  60.     }
  61. }
  62. bool sp(ull n) {
  63.     if (isP(n)) return true;
  64.     if (n <= 1e12) return false;
  65.     ull x = sqrt(n);
  66.     while (x * x > n) x--;
  67.     while ((x + 1) * (x + 1) <= n) x++;
  68.     ull a = 0, b = 0;
  69.     for (int i = 1;; i++) {
  70.         ull y = x + i;
  71.         if (isP(y)) {
  72.             a = y;
  73.             break;
  74.         }
  75.     }
  76.     for (int i = 0;; i--) {
  77.         ull y = x + i;
  78.         if (isP(y)) {
  79.             b = y;
  80.             break;
  81.         }
  82.     }
  83.     return n == a * b;
  84. }
  85. int main() {
  86.     fast;
  87.     gen();
  88.     int t; cin>>t;
  89.     for(int i=1;i<=t;++i){
  90.         ull n;
  91.         cin >> n;
  92.         if (mp[n] || sp(n)) cout << "NICE\n";
  93.         else cout << "UGLY\n";
  94.     }
  95.     return 0;
  96. }
Success #stdin #stdout 0.34s 65784KB
comments (?)
stdin
copy 
10
1
2
3
4
5
6
7
8
9
10
stdout
copy 
UGLY
NICE
NICE
UGLY
NICE
NICE
NICE
UGLY
UGLY
UGLY
https://ideone.com/evidDB
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!