結果

問題 No.376 立方体のN等分 (2)
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:29:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 739 ms / 5,000 ms
コード長 1,921 bytes
コンパイル時間 143 ms
コンパイル使用メモリ 81,528 KB
実行使用メモリ 85,060 KB
最終ジャッジ日時 2025-04-16 00:31:03
合計ジャッジ時間 6,459 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

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

def generate_divisors(factors):
    divisors = [1]
    for p in factors:
        exponents = [p**e for e in range(1, factors[p]+1)]
        new_divisors = []
        for d in divisors:
            for exp in exponents:
                new_divisors.append(d * exp)
        divisors += new_divisors
    divisors = list(set(divisors))
    divisors.sort()
    return divisors

def find_min_t(n):
    if n == 1:
        return 0
    factors = factorize(n)
    divisors = generate_divisors(factors)
    min_sum = float('inf')
    cube_root = round(n ** (1/3))
    max_a = cube_root
    for a in divisors:
        if a > max_a:
            continue
        if n % a != 0:
            continue
        m = n // a
        sub_factors = {}
        for p in factors:
            exp = 0
            temp = a
            while temp % p == 0:
                exp += 1
                temp //= p
            sub_factors[p] = factors[p] - exp
        m_divisors = generate_divisors(sub_factors)
        sqrt_m = math.isqrt(m)
        for b in m_divisors:
            if b < a:
                continue
            if b > sqrt_m:
                continue
            if m % b != 0:
                continue
            c = m // b
            if c < b:
                continue
            current_sum = a + b + c
            if current_sum < min_sum:
                min_sum = current_sum
    return min_sum - 3

n = int(input())
if n == 1:
    print("0 0")
else:
    tmin = find_min_t(n)
    tmax = n - 1
    print(f"{tmin} {tmax}")
0