結果

問題 No.1243 約数加算
コンテスト
ユーザー lam6er
提出日時 2025-03-26 16:00:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,274 bytes
コンパイル時間 283 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 74,052 KB
最終ジャッジ日時 2025-03-26 16:01:18
合計ジャッジ時間 5,787 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def get_divisors(n):
    divisors = set()
    for i in range(1, int(math.isqrt(n)) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return sorted(divisors, reverse=True)

def solve():
    import sys
    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
        
        path = []
        current = B
        found = False
        while current > A:
            delta = current - A
            if delta > 0 and A % delta == 0:
                path.append(delta)
                current = A
                break
            divisors = get_divisors(current)
            chosen = None
            for d in divisors:
                if d == current:
                    continue
                prev = current - d
                if prev >= A and prev % d == 0:
                    chosen = d
                    break
            if chosen is not None:
                path.append(chosen)
                current -= chosen
            else:
                path.append(1)
                current -= 1
        path.reverse()
        print(len(path))
        print(' '.join(map(str, path)))
        
solve()
0