結果

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

ソースコード

diff # 

import math

def prime_factors(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
    divisors = list(set(divisors))
    divisors.sort()
    return divisors

def find_min_sum(N):
    if N == 1:
        return 0
    factors_N = prime_factors(N)
    divisors = generate_divisors(factors_N)
    cube_root = round(N ** (1/3))
    a_candidates = [d for d in divisors if d <= cube_root]
    a_candidates.sort(reverse=True)  # Try larger a first

    min_sum = float('inf')

    for a in a_candidates:
        M = N // a
        if M == 0:
            continue
        # Compute factors of M by subtracting exponents from factors_N
        factors_a = {}
        temp_a = a
        for p in factors_N:
            cnt = 0
            while temp_a % p == 0:
                cnt += 1
                temp_a = temp_a // p
            if cnt > 0:
                factors_a[p] = cnt
        factors_M = {}
        for p in factors_N:
            exp_N = factors_N[p]
            exp_a = factors_a.get(p, 0)
            exp_M = exp_N - exp_a
            if exp_M > 0:
                factors_M[p] = exp_M
        # Generate divisors of M
        M_divisors = generate_divisors(factors_M)
        M_divisors.sort()
        sqrt_M = math.isqrt(M)
        for b in M_divisors:
            if b < a:
                continue  # Ensure a <= b
            if b > sqrt_M:
                continue
            if M % b != 0:
                continue
            c = M // b
            if b > c:
                continue
            if a <= b <= c:
                current_sum = a + b + c
                if current_sum < min_sum:
                    min_sum = current_sum
    if min_sum == float('inf'):
        return (N - 1) + 2  # If no valid split found, default to 1,1,N case sum
    return min_sum

def main():
    N = int(input().strip())
    if N == 1:
        print("0 0")
        return
    # Tmax is always N-1 (split into 1x1xN)
    Tmax = N - 1
    # Calculate Tmin
    min_sum = find_min_sum(N)
    if min_sum == 0:
        Tmin = 0
    else:
        Tmin = min_sum - 3
    print(Tmin, Tmax)

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