結果

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

ソースコード

diff # 

import sys
import math

def smallest_prime_factor(n):
    if n % 2 == 0:
        return 2
    max_divisor = int(math.isqrt(n)) + 1
    for i in range(3, max_divisor, 2):
        if n % i == 0:
            return i
    return n  # n is prime

def find_largest_divisor(current, max_d):
    if current <= max_d:
        return current
    spf = smallest_prime_factor(current)
    if spf == current:  # current is prime
        return 1
    candidate = current // spf
    if candidate <= max_d:
        return candidate
    else:
        # Iterate from max_d down to 1 to find the largest divisor
        # This is a fallback and may be slow for large max_d, but works for the problem's constraints
        for d in range(max_d, 0, -1):
            if current % d == 0:
                return d
        return 1

def solve_case(A, B):
    steps = []
    current = B
    while current > A:
        max_d = current - A
        d = find_largest_divisor(current, max_d)
        steps.append(d)
        current -= d
    steps.reverse()
    return steps

def main():
    input = sys.stdin.read().split()
    T = int(input[0])
    idx = 1
    for _ in range(T):
        A = int(input[idx])
        B = int(input[idx+1])
        idx +=2
        steps = solve_case(A, B)
        print(len(steps))
        print(' '.join(map(str, steps)))

if __name__ == "__main__":
    main()
0