結果

問題 No.375 立方体のN等分 (1)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:37:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,383 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,732 KB
実行使用メモリ 69,564 KB
最終ジャッジ日時 2025-03-20 20:37:56
合計ジャッジ時間 3,013 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def compute_min_sum(N):
    min_sum = float('inf')

    # Type 1: a, a, b where a² * b = N and a <= b
    max_a_type1 = int(math.isqrt(N))  # Maximum a such that a² <= N
    for a in range(1, max_a_type1 + 1):
        if N % (a * a) == 0:
            b = N // (a * a)
            if a <= b:
                current_sum = 2 * a + b
                if current_sum < min_sum:
                    min_sum = current_sum

    # Type 2: a, b, b where a * b² = N and a <= b
    # Collect all divisors of N
    divisors = set()
    for i in range(1, int(math.isqrt(N)) + 1):
        if N % i == 0:
            divisors.add(i)
            divisors.add(N // i)
    # Check each divisor b
    for b in divisors:
        m = N // b
        sqrt_m = int(math.isqrt(m))
        if sqrt_m * sqrt_m == m and sqrt_m <= b:
            a = sqrt_m
            current_sum = a + 2 * b
            if current_sum < min_sum:
                min_sum = current_sum

    # Type 3: a, a, a where a³ = N
    cube_root = round(N ** (1/3))
    if cube_root ** 3 == N:
        current_sum = 3 * cube_root
        if current_sum < min_sum:
            min_sum = current_sum

    # If no valid decomposition is found (always exists as 1x1xN)
    if min_sum == float('inf'):
        min_sum = 1 + 1 + N

    return min_sum

N = int(input())
tmin = compute_min_sum(N) - 3
tmax = N - 1
print(tmin, tmax)
0