QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#706970#6566. Power of Divisorstassei903#RE 15ms10764kbPython31.1kb2024-11-03 14:11:042024-11-03 14:11:04

Judging History

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

  • [2024-11-03 14:11:04]
  • 评测
  • 测评结果:RE
  • 用时:15ms
  • 内存:10764kb
  • [2024-11-03 14:11:04]
  • 提交

answer


from math import floor
def f(n, e):
    if e <= 3:
        ok = 0
        ng = 10 ** 18
        while ng - ok > 1:
            mid = ok + ng >> 1
            if mid ** e <= n:
                ok = mid
            else:
                ng = mid
        if ok ** e == n:
            return ok
    else:
        for x in range(1, 10 ** 18):
            if x ** e > n:
                return -1
            if x ** e == n:
                return x

def divisors(n):
    a = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            a.append(i)
            if n // i != i:
                a.append(n//i)
        i += 1
    
    return a

n = int(input())
if n == 1:
    print(1)
    exit()
b, e = n, 1
for i in range(63, 1, -1):
    x = f(n, i)
    if x == -1:
        continue
    b, e = x, i
    break

if e == 1:
    print(-1)
    exit()
# print(b)
ans = 10 ** 20
for j in divisors(e):
    if j == e:
        continue
    x = b ** j
    if len(divisors(x)) == e // j:
        ans = min(ans, x)

if ans == 10 ** 20:
    print(-1)
else:
    print(ans)

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 10704kb

input:

15625

output:

25

result:

ok single line: '25'

Test #2:

score: 0
Accepted
time: 15ms
memory: 10716kb

input:

64000000

output:

20

result:

ok single line: '20'

Test #3:

score: 0
Accepted
time: 3ms
memory: 10764kb

input:

65536

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 14ms
memory: 10764kb

input:

1

output:

1

result:

ok single line: '1'

Test #5:

score: -100
Dangerous Syscalls

input:

10

output:


result: