Advertisement
pb_jiang

CF1846E2 WA

Jul 8th, 2023
862
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.19 KB | None | 0 0
  1. #include <assert.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #ifndef __DEBUG__
  5. #define dbg(...) 42
  6. #endif
  7. template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
  8.  
  9. using ll = long long;
  10. using pii = pair<int, int>;
  11. using pll = pair<ll, ll>;
  12. using vl = vector<ll>;
  13. using vi = vector<int>;
  14. using ull = unsigned long long;
  15. using ld = long double;
  16.  
  17. // constexpr ll p1 = (1ll << 50) - 51, p2 = (1ll << 50) - 117;
  18. constexpr ll p1 = (1ll << 30) - 35, p2 = (1ll << 30) - 41;
  19.  
  20. ll fpow(ll b, ll p, ll m)
  21. {
  22.     ll ret = 1;
  23.     ll cur = b;
  24.     while (p) {
  25.         if (p % 2)
  26.             ret = ret * cur % m;
  27.         cur = cur * cur % m;
  28.         p /= 2;
  29.     }
  30.     return ret;
  31. }
  32.  
  33. int main(int argc, char **argv)
  34. {
  35.     ll t, n;
  36.     cin >> t;
  37.     while (t--) {
  38.         cin >> n;
  39.         bool ok = false;
  40.         for (ll p = 3; p <= 95 && !ok; ++p) {
  41.             ll lb = 2, ub = 1e9;
  42.             // auto f = [p](ll k) { return (pow(double(k), double(p)) - 1) / (double) (k - 1); };
  43.             auto f = [p](ll k) { return (powl(k, p) - 1) / (k - 1); };
  44.             while (lb + 1 < ub) {
  45.                 ll mid = (lb + ub) / 2;
  46.                 if (f(mid) <= n)
  47.                     lb = mid;
  48.                 else
  49.                     ub = mid;
  50.             }
  51.             if (f(lb) == n)
  52.                 ok = true;
  53.         }
  54.         if (!ok) {
  55.             auto f = [](ll k) { return 1 + k + k * k; };
  56.             ll lb = 2, ub = 1e9;
  57.             while (lb + 1 < ub) {
  58.                 ll mid = (lb + ub) / 2;
  59.                 if (f(mid) <= n)
  60.                     lb = mid;
  61.                 else
  62.                     ub = mid;
  63.             }
  64.             if (f(lb) == n)
  65.                 ok = true;
  66.         }
  67.         if (!ok) {
  68.             auto f = [](ld k) { return 1 + k + k * k + k * k * k; };
  69.             ll lb = 2, ub = 1e9;
  70.             while (lb + 1 < ub) {
  71.                 ll mid = (lb + ub) / 2;
  72.                 if (f(mid) <= n)
  73.                     lb = mid;
  74.                 else
  75.                     ub = mid;
  76.             }
  77.             if (f(lb) == ld(n))
  78.                 ok = true;
  79.         }
  80.         cout << (ok ? "YES" : "NO") << endl;
  81.     }
  82.     return 0;
  83. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement