結果
問題 | No.2104 Multiply-Add |
ユーザー |
👑 ![]() |
提出日時 | 2022-10-21 22:47:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,468 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 82,200 KB |
実行使用メモリ | 54,316 KB |
最終ジャッジ日時 | 2024-07-01 07:13:05 |
合計ジャッジ時間 | 2,914 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
def operate(x,y,T): for t,k in T: if t==1: x+=k*y else: y+=k*x return x,y def solve(): from math import gcd a,b,c,d=map(int,input().split()) if gcd(a,b)!=gcd(c,d): print(-1) return if gcd(a,b)==0: print(0) return def euclid(a,b): res=[] while a and b: if abs(a)>abs(b): k=abs(a)//abs(b) x=a+k*b; y=a-k*b if abs(x)<abs(y): res.append((1,k)) a+=k*b else: res.append((1,-k)) a-=k*b else: k=abs(b)//abs(a) x=b+k*a; y=b-k*a if abs(x)<abs(y): res.append((2,k)) b+=k*a else: res.append((2,-k)) b-=k*a return res T1=euclid(a,b); a2,b2=operate(a,b,T1) T2=euclid(c,d); c2,d2=operate(c,d,T2) T3=[] if a2==0: a2,b2=b2,a2 T3=[(1,1),(2,-1)] T4=[] if c2==0: c2,d2=d2,c2 T4=[(1,1),(2,-1)] T5=[] if a2*c2<0: T5=[(2,-2),(1,1),(2,-2)] T2=[(t,-k) for t,k in T2][::-1] T4=[(t,-k) for t,k in T4][::-1] T=T1+T3+T5+T4+T2 print(len(T)) for t,k in T: print(t,k) #================================================== solve()