結果

問題 No.2104 Multiply-Add
ユーザー shotoyooshotoyoo
提出日時 2022-10-21 22:14:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 92 ms / 2,000 ms
コード長 3,482 bytes
コンパイル時間 1,564 ms
コンパイル使用メモリ 86,612 KB
実行使用メモリ 72,276 KB
最終ジャッジ日時 2023-09-13 22:36:24
合計ジャッジ時間 5,625 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 90 ms
71,972 KB
testcase_01 AC 91 ms
71,784 KB
testcase_02 AC 92 ms
71,740 KB
testcase_03 AC 91 ms
71,836 KB
testcase_04 AC 92 ms
71,736 KB
testcase_05 AC 92 ms
71,912 KB
testcase_06 AC 90 ms
71,916 KB
testcase_07 AC 91 ms
71,876 KB
testcase_08 AC 90 ms
71,932 KB
testcase_09 AC 90 ms
72,164 KB
testcase_10 AC 90 ms
71,920 KB
testcase_11 AC 89 ms
71,904 KB
testcase_12 AC 91 ms
71,920 KB
testcase_13 AC 90 ms
71,932 KB
testcase_14 AC 89 ms
71,900 KB
testcase_15 AC 90 ms
71,828 KB
testcase_16 AC 90 ms
71,788 KB
testcase_17 AC 91 ms
71,848 KB
testcase_18 AC 90 ms
71,904 KB
testcase_19 AC 89 ms
71,912 KB
testcase_20 AC 90 ms
71,956 KB
testcase_21 AC 90 ms
71,852 KB
testcase_22 AC 89 ms
71,684 KB
testcase_23 AC 89 ms
71,832 KB
testcase_24 AC 89 ms
71,904 KB
testcase_25 AC 88 ms
71,792 KB
testcase_26 AC 89 ms
72,276 KB
testcase_27 AC 90 ms
71,880 KB
testcase_28 AC 88 ms
71,804 KB
testcase_29 AC 90 ms
71,908 KB
testcase_30 AC 90 ms
71,916 KB
testcase_31 AC 90 ms
72,060 KB
testcase_32 AC 91 ms
71,956 KB
testcase_33 AC 90 ms
71,944 KB
testcase_34 AC 91 ms
71,744 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys, random
input = lambda : sys.stdin.readline().rstrip()


write = lambda x: sys.stdout.write(x+"\n"); writef = lambda x: print("{:.12f}".format(x))
debug = lambda x: sys.stderr.write(x+"\n")
YES="Yes"; NO="No"; pans = lambda v: print(YES if v else NO); INF=10**18
LI = lambda : list(map(int, input().split())); II=lambda : int(input()); SI=lambda : [ord(c)-ord("a") for c in input()]
def debug(_l_):
    for s in _l_.split():
        print(f"{s}={eval(s)}", end=" ")
    print()
def dlist(*l, fill=0):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [dlist(*ll, fill=fill) for _ in range(l[0])]

a,b,c,d = list(map(int, input().split()))
def main(a,b,c,d):
# if 1:
    a0 = a
    b0 = b
    c0 = c
    d0 = d
    def gcd(a,b):
        if a==0 or b==0:
            return []
        if abs(a)>abs(b):
            t = 1
            k = a//b
            na = a%b
            nb = b
        else:
            t = 2
            k = b//a
            na = a
            nb = b%a
        return [(t,-k,na,nb)] + gcd(na,nb)
    import math
    g1 = math.gcd(a,b)
    g2 = math.gcd(c,d)
    if g2!=g1:
        print(-1)
    else:
        def sub(a,b):
            l0 = []
            if a<0:
                if b==0:
                    l0.extend([(2,-1), (1, 1)])
                    a = 0
                    b = -a
                elif b>0:
                    d,m = divmod(abs(a), abs(b))
                    l0.append((1, d+1))
                    a += (d+1)*b
                else:
                    d,m = divmod(abs(a), abs(b))
                    l0.append((1, -(d+1)))
                    a += -(d+1)*b
                    if a==0:
                        l0.extend([(1,-1), (2,1)])
                        a = -b
                        b = 0
                    else:
                        assert a>0
                        d,m = divmod(abs(b), abs(a))
                        l0.append((2, (d+1)))
                        b += a*(d+1)
            elif a==0:
                if b<0:
                    l0.extend([(1,-1), (2,1)])
                    a = -b
                    b = 0
            else:
                if b<0:
                    # a>0
                    d,m = divmod(abs(b), a)
                    l0.append((2, d+1))
                    b += (d+1)*a
            assert a>=0 and b>=0, breakpoint()
            return a,b,l0
        a,b,l0 = sub(a,b)
        c,d,l1 = sub(c,d)

        res = gcd(a,b)
        res2 = gcd(c,d)
        if res:
            _,_,aa,bb = res[-1]
        else:
            aa,bb = a,b
        if res2:
            _,_,aa2,bb2 = res2[-1]
        else:
            aa2,bb2 = c,d
        if aa==aa2:
            pass
        else:
            if aa>0:
                res.append((2,1,None,None))
                res.append((1,-1,None,None))
            else:
                res.append((1,1,None,None))
                res.append((2,-1,None,None))
        for t,k,*_ in res2[::-1]:
            res.append((t,-k,None,None))
        res0 = res[:]

        res = l0 + res
        for t,k,*_ in l1[::-1]:
            res.append((t,-k))
        def check(res,aa,bb):
            for t,k,*_ in res:
                if t==1:
                    aa += k*bb
                else:
                    bb += k*aa
            return aa,bb
        aa,bb = check(res, a0,b0)
        assert aa==c0 and bb==d0
        print(len(res))
        for item in res:
            write(" ".join(map(str, item[:2])))
main(a,b,c,d)
0