結果

問題 No.1243 約数加算
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-02-24 15:57:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 897 bytes
コンパイル時間 381 ms
コンパイル使用メモリ 82,092 KB
実行使用メモリ 90,732 KB
最終ジャッジ日時 2024-09-24 17:06:14
合計ジャッジ時間 2,538 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
53,048 KB
testcase_01 AC 36 ms
52,868 KB
testcase_02 AC 36 ms
54,264 KB
testcase_03 AC 38 ms
53,412 KB
testcase_04 AC 76 ms
78,132 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**7)
memo={}
def main(a,b):
  if (a,b) in memo:return memo[(a,b)]
  if b-a<3:return [1]*(b-a)
  if b==a:return []
  if b==a+1:return [1]
  if b==a+2 and a%2==0:return [2]
  if b==a+2:return [1,1]
  if 2*a<=b:
    ret=[a]+main(2*a,b)
    memo[(a,b)]=ret
    return ret
  ary=[]
  if a%2==1:
    ary.append(1)
    a+=1
  d=2
  while a+a//d>b and a%(2*d)==0:
    d*=2
  if a+a//d<=b:
    ary.append(a//d)
    ary+=main(a+a//d,b)
    memo[(a,b)]=ary
    return ary
  else:
    while a+d>b:
      d//=2
    ary.append(d)
    ary+=main(a+d,b)
    memo[(a,b)]=ary
    return ary
def chk(a,b,ret):
  if len(ret)>120:return False,0,ret
  for x in ret:
    if a%x==0:
      a+=x
    else:
      return False,1,ret
  return a==b,2,ret
t=int(input())
cases=[list(map(int,input().split())) for _ in range(t)]
for a,b in cases:
  ret=main(a,b)
  print(len(ret))
  print(*ret)
0