結果

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

ソースコード

diff # 

import math

def find_max_d(current, A):
    if current == A:
        return None
    # Check even case first
    if current % 2 == 0:
        candidate = current // 2
        if candidate <= current - A:
            return candidate
    # Check current - A as a candidate
    candidate = current - A
    if candidate > 0 and current % candidate == 0 and candidate < current:
        return candidate
    max_div = 0
    sqrt_current = int(math.isqrt(current))
    for i in range(1, sqrt_current + 1):
        if current % i == 0:
            d1 = i
            d2 = current // i
            for d in [d2, d1]:
                if d < current and (current - d) >= A:
                    if d > max_div:
                        max_div = d
    if max_div != 0:
        return max_div
    else:
        # Must choose d = current - A, which should divide A
        d = current - A
        return d

def solve_case(A, B):
    path = []
    current = B
    while current != A:
        d = find_max_d(current, A)
        if d is None:
            break
        path.append(d)
        current -= d
        if len(path) > 120:
            assert False, "Exceeded step limit"
    path.reverse()
    return path

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

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