結果

問題 No.1243 約数加算
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:26:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,732 bytes
コンパイル時間 337 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 68,860 KB
最終ジャッジ日時 2025-05-14 13:27:30
合計ジャッジ時間 4,603 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def get_largest_divisor_le_target(n, target_max_d):
    best_d = 1 # Initialize with 1. Since target_max_d >= 1, 1 is always a valid candidate.
    
    limit = int(math.sqrt(n))
    for i in range(1, limit + 1):
        if n % i == 0:
            # Divisor i
            if i <= target_max_d:
                if i > best_d:
                    best_d = i
            
            # Divisor n // i
            # Only consider if it's different from i (i.e. n is not i*i)
            # or handle it once. If i*i = n, then d2 = i.
            d2 = n // i
            if d2 <= target_max_d:
                if d2 > best_d:
                    best_d = d2
    return best_d

def solve():
    A, B = map(int, input().split())

    current_val = B
    reversed_ops = []

    while current_val > A:
        target_max_d = current_val - A
        
        chosen_d = get_largest_divisor_le_target(current_val, target_max_d)
        
        reversed_ops.append(chosen_d)
        current_val -= chosen_d
        
        # According to problem constraints (K <= 120), this explicit check might not be strictly necessary
        # if the strategy is guaranteed to finish within 120 steps.
        # if len(reversed_ops) > 120:
        #     break 

    ops = reversed_ops[::-1]
    print(len(ops))
    if len(ops) > 0:
        print(*(ops))
    else:
        # This case implies A == B initially. Problem constraints state A < B.
        # If A could be equal to B, and K must be >= 1 as per output format,
        # this branch might need adjustment. But given A < B, len(ops) >= 1.
        print() # Or handle as error / assert false depending on strict interpretation for A=B.


T = int(input())
for _ in range(T):
    solve()
0