結果

問題 No.1243 約数加算
ユーザー gew1fw
提出日時 2025-06-12 20:29:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,139 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,052 KB
実行使用メモリ 65,872 KB
最終ジャッジ日時 2025-06-12 20:29:50
合計ジャッジ時間 4,174 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def find_largest_divisor(c, d_limit):
    if d_limit < 1:
        return 0
    max_div = 0
    # Check from the minimum of c//2 and d_limit down to 1
    start = min(c // 2, d_limit)
    for candidate in range(start, 0, -1):
        if c % candidate == 0:
            max_div = candidate
            break
    # If not found, check if c itself is within d_limit, but c > A so c - c = 0 < A
    return max_div if max_div != 0 else 1

def solve():
    input = sys.stdin.read().split()
    idx = 0
    T = int(input[idx])
    idx += 1
    for _ in range(T):
        A = int(input[idx])
        B = int(input[idx+1])
        idx +=2
        if A == B:
            print(0)
            print()
            continue
        steps = []
        C = B
        while C > A:
            D = C - A
            # Find largest d that divides C and d <= D
            d = find_largest_divisor(C, D)
            steps.append(d)
            C -= d
        # Now, reverse the steps to get the addition sequence
        steps = steps[::-1]
        print(len(steps))
        print(' '.join(map(str, steps)))

if __name__ == '__main__':
    solve()
0