結果

問題 No.376 立方体のN等分 (2)
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:28:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 436 ms / 5,000 ms
コード長 2,541 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 78,632 KB
最終ジャッジ日時 2025-04-16 16:29:43
合計ジャッジ時間 5,007 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import math

def factorize(n):
    factors = {}
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n = n // 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n = n // i
        i += 2
    if n > 1:
        factors[n] = 1
    return factors

def generate_divisors(factors):
    divisors = [1]
    for p, exp in factors.items():
        temp = []
        for d in divisors:
            current = d
            for e in range(1, exp + 1):
                current *= p
                temp.append(current)
        divisors += temp
    return sorted(divisors)

def integer_cube_root(n):
    low = 1
    high = n
    while low <= high:
        mid = (low + high) // 2
        cube = mid ** 3
        if cube == n:
            return mid
        elif cube < n:
            low = mid + 1
        else:
            high = mid - 1
    return high

def get_prime_factors(a, original_factors):
    factors = {}
    for p in original_factors:
        count = 0
        while a % p == 0:
            count += 1
            a = a // p
        if count > 0:
            factors[p] = count
    return factors

def subtract_factors(original_factors, a_factors):
    m_factors = {}
    for p in original_factors:
        exp = original_factors[p] - a_factors.get(p, 0)
        if exp > 0:
            m_factors[p] = exp
    return m_factors

def find_max_b(m_factors):
    divisors = generate_divisors(m_factors)
    m = 1
    for p, e in m_factors.items():
        m *= p ** e
    sqrt_m = int(math.isqrt(m))
    max_b = 1
    for d in divisors:
        if d <= sqrt_m and d > max_b:
            max_b = d
    return max_b

def main():
    N = int(input().strip())
    if N == 1:
        print("0 0")
        return
    original_factors = factorize(N)
    divisors = generate_divisors(original_factors)
    cube_root = integer_cube_root(N)
    min_sum = float('inf')
    for a in divisors:
        if a > cube_root:
            continue
        if N % a != 0:
            continue
        M = N // a
        a_factors = get_prime_factors(a, original_factors)
        m_factors = subtract_factors(original_factors, a_factors)
        if not m_factors:
            b = 1
            c = 1
        else:
            b = find_max_b(m_factors)
            c = M // b
        current_sum = a + b + c
        if current_sum < min_sum:
            min_sum = current_sum
    Tmin = min_sum - 3
    Tmax = N - 1
    print(f"{Tmin} {Tmax}")

if __name__ == "__main__":
    main()
0