結果

問題 No.2104 Multiply-Add
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:02:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,441 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,732 KB
実行使用メモリ 54,816 KB
最終ジャッジ日時 2025-04-09 21:03:49
合計ジャッジ時間 5,136 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def readints():
    return list(map(int, sys.stdin.readline().split()))

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def main():
    a, b, c, d = readints()

    # Case 0: already target
    if a == c and b == d:
        print(0)
        return

    # Case for (a, b) = (0, 0)
    if a == 0 and b == 0:
        print(-1)
        return

    # Compute gcd for initial and target
    g_initial = gcd(a, b)
    g_target = gcd(c, d)

    if g_initial != g_target:
        print(-1)
        return

    # Handle cases with a == 0 or b == 0
    if a == 0:
        if c != 0:
            print(-1)
            return
        else:
            if d == b:
                print(0)
                return
            else:
                print(-1)
                return
    if b == 0:
        if d != 0:
            print(-1)
            return
        else:
            if c == a:
                print(0)
                return
            else:
                print(-1)
                return

    # Now handle cases where both a and b are non-zero

    # Try two-step approach: operation 1 then 2
    # Step 1: x = a + k1*b = c
    if (c - a) % b == 0:
        k1 = (c - a) // b
        x1 = a + k1 * b
        if x1 < -1e9 or x1 > 1e9:
            pass
        else:
            # Step 2: y = b + k2*x1 = d
            if (d - b) % x1 == 0:
                k2 = (d - b) // x1
                y2 = b + k2 * x1
                if y2 >= -1e9 and y2 <= 1e9:
                    print(2)
                    print(1, k1)
                    print(2, k2)
                    return

    # Try two-step approach: operation 2 then 1
    if (d - b) % a == 0:
        k2 = (d - b) // a
        y1 = b + k2 * a
        if y1 < -1e9 or y1 > 1e9:
            pass
        else:
            # Step 2: x = a + k1*y1 = c
            if (c - a) % y1 == 0:
                k1 = (c - a) // y1
                x2 = a + k1 * y1
                if x2 >= -1e9 and x2 <= 1e9:
                    print(2)
                    print(2, k2)
                    print(1, k1)
                    return

    # Now attempt the four-step approach
    # s = (d + c - b - a)
    s = (c + d - b - a)
    if b != 0 and s % b == 0:
        k1 = s // b
        x1 = a + k1 * b
        y2 = c + d
        if x1 < -1e9 or x1 > 1e9 or y2 < -1e9 or y2 > 1e9:
            pass
        else:
            numerator_c = c - x1
            if y2 == 0:
                pass
            elif numerator_c % y2 == 0:
                k3 = numerator_c // y2
                x3 = x1 + k3 * y2
                if x3 != c:
                    pass
                else:
                    numerator_d = d - y2
                    if c == 0:
                        pass
                    elif numerator_d % c == 0:
                        k4 = numerator_d // c
                        y4 = y2 + k4 * c
                        if y4 == d:
                            # Check all intermediate steps
                            # step1: after operation1 k1 x1 = a +k1*b, y remains b
                            if abs(x1) > 1e9:
                                pass
                            else:
                                # step2: operation2 k2. y becomes y2 = b + k2*x1
                                # in four-step approach, k2 is 1
                                k2 = 1
                                y2_calc = b + k2 * x1
                                if y2_calc != y2:
                                    pass
                                else:
                                    # step3: operation1 k3 x3 =x1 +k3*y2_calc
                                    if abs(y2_calc) > 1e9 or abs(x3) > 1e9:
                                        pass
                                    else:
                                        # step4: operation2 k4. y4 = y2 +k4*x3
                                        if abs(y4) > 1e9:
                                            pass
                                        else:
                                            print(4)
                                            print(1, k1)
                                            print(2, 1)
                                            print(1, k3)
                                            print(2, k4)
                                            return

    # If no approach works
    print(-1)

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