QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#709158#6566. Power of Divisorstassei903WA 15ms10768kbPython31.2kb2024-11-04 12:27:172024-11-04 12:27:18

Judging History

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

  • [2024-11-04 12:27:18]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:10768kb
  • [2024-11-04 12:27:17]
  • 提交

answer

from math import floor
def kth_root_integer(a: int, k: int) -> int:
    if a <= 1 or k == 1: return a
    if 64 <= k: return 1
    def check(n: int) -> bool:
        x = 1; m = n
        p = k
        while p:
            if p & 1: x *= m
            p >>= 1
            m *= m
        return x <= a
    n = int(pow(a, 1 / k))
    while not check(n): n -= 1
    while check(n + 1): n += 1
    return n

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
def solve():
    n = int(input())
    if n == 1:
        print(1)
        return
    b, e = n, 1
    for i in range(63, 1, -1):
        x = kth_root_integer(n, i)
        if x == -1:
            continue
        b, e = x, i
        break

    if e == 1:
        print(-1)
        return
    ans = 10 ** 20
    for j in sorted(divisors(e))[:-1]:
        x = b ** j
        if len(divisors(x)) == e // j:
            print(x)
            break
    else:
        print(-1)

solve()
# for _ in range(int(input())):
#     solve()

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 15ms
memory: 10768kb

input:

15625

output:

-1

result:

wrong answer 1st lines differ - expected: '25', found: '-1'