結果

問題 No.375 立方体のN等分 (1)
ユーザー lam6er
提出日時 2025-03-20 20:18:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 298 ms / 5,000 ms
コード長 1,217 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 76,992 KB
最終ジャッジ日時 2025-03-20 20:20:05
合計ジャッジ時間 3,539 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def find_min_max_planes(N):
    # Compute Tmax
    Tmax = N - 1
    
    # Function to generate all factors of a number M >=1
    def get_factors(M):
        factors = set()
        for i in range(1, int(math.isqrt(M)) + 1):
            if M % i == 0:
                factors.add(i)
                factors.add(M // i)
        return sorted(factors)
    
    min_sum = float('inf')
    max_cube_root = int(round(N ** (1/3))) + 1
    for p in range(1, max_cube_root + 1):
        if N % p != 0:
            continue
        M = N // p
        factors_M = get_factors(M)
        for q in factors_M:
            if q < p:
                continue
            if q > math.isqrt(M):
                continue
            if M % q != 0:
                continue
            r = M // q
            if r < q:
                continue
            current_sum = p + q + r
            if current_sum < min_sum:
                min_sum = current_sum
    if min_sum == float('inf'):
        # In case N is prime, min_sum is 1+1+N, Tmin = (1+1+N) -3 = N-1
        Tmin = Tmax
    else:
        Tmin = min_sum - 3
    return Tmin, Tmax

# Read input
N = int(input())
Tmin, Tmax = find_min_max_planes(N)
print(Tmin, Tmax)
0