QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#111397#6566. Power of Divisorshos_lyricAC ✓2ms3824kbC++143.0kb2023-06-06 22:54:452023-06-06 22:54:47

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-06 22:54:47]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3824kb
  • [2023-06-06 22:54:45]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


// floor(a^(1/k))
unsigned long long floorKthRoot(unsigned long long a, unsigned long long k) {
  if (a == 0) {
    return 0;
  } else if (k <= 1) {
    return a;
  } else if (k == 2) {
    unsigned long long b = a, x = 0, y = 0;
    for (int e = (63 - __builtin_clzll(a)) & ~1; e >= 0; e -= 2) {
      x <<= 1;
      y <<= 1;
      if (b >= (y | 1) << e) {
        b -= (y | 1) << e;
        x |= 1;
        y += 2;
      }
    }
    return x;
  } else if (k <= 40) {
    // min x s.t. x^k >= 2^64
    static constexpr unsigned long long HIS[] =
        {0, 0, 4294967296ULL, 2642246, 65536, 7132, 1626, 566, 256, 139, 85, 57,
         41, 31, 24, 20, 16, 14, 12, 11, 10, 9, 8, 7, 7, 6, 6, 6, 5, 5, 5, 5,
         4, 4, 4, 4, 4, 4, 4, 4, 4};
    const int bsr = 63 - __builtin_clzll(a);
    unsigned long long lo = 1ULL << (bsr / k);
    unsigned long long hi = std::min(1ULL << (bsr / k + 1), HIS[k]);
    for (; lo + 1 < hi; ) {
      const unsigned long long mid = (lo + hi) / 2;
      unsigned long long b = mid * mid;
      for (unsigned i = 2; i < k; ++i) b *= mid;
      ((b <= a) ? lo : hi) = mid;
    }
    return lo;
  } else if (k <= 63) {
    return ((1ULL << k) <= a) ? 2 : 1;
  } else {
    return 1;
  }
}


int main() {
  Int X;
  for (; ~scanf("%lld", &X); ) {
    Int ans = -1;
    if (X == 1) {
      ans = 1;
    } else {
      for (Int e = 60; e >= 2; --e) {
        const Int n = floorKthRoot(X, e);
        Int ne = 1;
        for (int i = 0; i < e; ++i) ne *= n;
        if (ne == X) {
          int cnt = 0;
          for (Int d = 1; d * d <= n; ++d) if (n % d == 0) {
            ++cnt;
            if (d != n/d) ++cnt;
          }
          if (cnt == e) {
            ans = n;
            goto found;
          }
        }
      }
     found:{}
    }
    printf("%lld\n", ans);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3816kb

input:

15625

output:

25

result:

ok single line: '25'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

64000000

output:

20

result:

ok single line: '20'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

65536

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3528kb

input:

1

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

10

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

100

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

10000

output:

10

result:

ok single line: '10'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

1000000000000000000

output:

100

result:

ok single line: '100'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3564kb

input:

10372926089038969

output:

218089

result:

ok single line: '218089'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

10642944803293201

output:

10157

result:

ok single line: '10157'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3564kb

input:

10646534823110209

output:

103182047

result:

ok single line: '103182047'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

1073741824

output:

32

result:

ok single line: '32'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

121

output:

11

result:

ok single line: '11'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3612kb

input:

1296

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3820kb

input:

16

output:

-1

result:

ok single line: '-1'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

16277421889

output:

127583

result:

ok single line: '127583'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3604kb

input:

169

output:

13

result:

ok single line: '13'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

1985984

output:

-1

result:

ok single line: '-1'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

2

output:

-1

result:

ok single line: '-1'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

205891132094649

output:

243

result:

ok single line: '243'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

25

output:

5

result:

ok single line: '5'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

2626114239841

output:

1273

result:

ok single line: '1273'

Test #23:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

26269395104446321

output:

12731

result:

ok single line: '12731'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

3

output:

-1

result:

ok single line: '-1'

Test #25:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

3596345248055296

output:

88

result:

ok single line: '88'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

36

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0
Accepted
time: 2ms
memory: 3668kb

input:

4

output:

2

result:

ok single line: '2'

Test #28:

score: 0
Accepted
time: 2ms
memory: 3612kb

input:

4096

output:

8

result:

ok single line: '8'

Test #29:

score: 0
Accepted
time: 2ms
memory: 3524kb

input:

49

output:

7

result:

ok single line: '7'

Test #30:

score: 0
Accepted
time: 2ms
memory: 3668kb

input:

5

output:

-1

result:

ok single line: '-1'

Test #31:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

576460752303423488

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0
Accepted
time: 2ms
memory: 3612kb

input:

581431415926321

output:

24112889

result:

ok single line: '24112889'

Test #33:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

6

output:

-1

result:

ok single line: '-1'

Test #34:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

64

output:

4

result:

ok single line: '4'

Test #35:

score: 0
Accepted
time: 2ms
memory: 3548kb

input:

656100000000

output:

30

result:

ok single line: '30'

Test #36:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

7

output:

-1

result:

ok single line: '-1'

Test #37:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

729

output:

9

result:

ok single line: '9'

Test #38:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

8

output:

-1

result:

ok single line: '-1'

Test #39:

score: 0
Accepted
time: 2ms
memory: 3808kb

input:

81

output:

-1

result:

ok single line: '-1'

Test #40:

score: 0
Accepted
time: 2ms
memory: 3616kb

input:

8527674378686464

output:

452

result:

ok single line: '452'

Test #41:

score: 0
Accepted
time: 2ms
memory: 3620kb

input:

9

output:

3

result:

ok single line: '3'

Test #42:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

982134461213542729

output:

994009

result:

ok single line: '994009'

Test #43:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

9992002399680016

output:

9998

result:

ok single line: '9998'

Test #44:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

999269311525198921

output:

-1

result:

ok single line: '-1'

Test #45:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

999949000866995087

output:

-1

result:

ok single line: '-1'

Test #46:

score: 0
Accepted
time: 2ms
memory: 3668kb

input:

999995482005103081

output:

-1

result:

ok single line: '-1'

Test #47:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

999999969999997921

output:

-1

result:

ok single line: '-1'

Test #48:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

999999999999999989

output:

-1

result:

ok single line: '-1'

Test #49:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

999999999999999999

output:

-1

result:

ok single line: '-1'