結果

問題 No.2610 Decreasing LCMs
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:07:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 959 bytes
コンパイル時間 242 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 54,480 KB
最終ジャッジ日時 2025-06-12 16:07:11
合計ジャッジ時間 4,579 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def construct_sequence(N):
    if N == 3:
        return [21, 24, 144]
    sequence = []
    a = 2
    b = 3
    sequence.append(a)
    sequence.append(b)
    for i in range(2, N):
        # Choose c such that LCM(b, c) < LCM(a, b)
        # Since a and b are coprime, LCM(a, b) = a*b
        # We need a*b > c and c must be a multiple of b
        # Let's choose c = 2*b, but check if a*b > c
        # For a=2, b=3: c=6, but 2*3 =6, so 6 >6 is false.
        # So, we need c < a*b, and c must be a multiple of b
        # Let's try c = b * (a-1)
        c = b * (a // 2)  # For a=2, c=3*1=3, but c must be >b
        if c <= b:
            c = b + 1
        while True:
            if c > b and (b * c) // gcd(b, c) < (a * b):
                break
            c += 1
        sequence.append(c)
        a, b = b, c
    return sequence

import math

def gcd(x, y):
    return math.gcd(x, y)

# Example for N=3
print(' '.join(map(str, construct_sequence(3))))
0