結果

問題 No.2104 Multiply-Add
ユーザー SumitacchanSumitacchan
提出日時 2022-08-28 18:50:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,790 bytes
コンパイル時間 2,091 ms
コンパイル使用メモリ 203,844 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-05 19:16:08
合計ジャッジ時間 5,265 ms
ジャッジサーバーID
(参考情報)
judge14 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,384 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 1 ms
4,380 KB
testcase_29 AC 2 ms
4,376 KB
testcase_30 AC 2 ms
4,380 KB
testcase_31 AC 2 ms
4,376 KB
testcase_32 AC 1 ms
4,376 KB
testcase_33 AC 1 ms
4,376 KB
testcase_34 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

using Pll = pair<ll, ll>;

void operation(ll t, ll k, ll &x, ll &y, vector<Pll> &ans){
    if(t == 1){
        ans.push_back(Pll(1, k));
        x += k * y;
    }else if(t == 2){
        ans.push_back(Pll(2, k));
        y += k * x;
    }else{
        assert(false);
    }
}

// (x,y) -> (g,0) にする手順を求める
vector<Pll> normalize(ll x, ll y){
    vector<Pll> ans;
    
    while(min(x, y) < 0){
        if(x < 0){
            // (x,y)->(y,-x)
            operation(2, -1, x, y, ans);
            operation(1, 1, x, y, ans);
            operation(2, -1, x, y, ans);
        }else if(y < 0){
            // (x,y)->(-y,x)
            operation(1, -1, x, y, ans);
            operation(2, 1, x, y, ans);
            operation(1, -1, x, y, ans);
        }
    }

    // 互除法
    while(min(x, y) > 0){
        if(x >= y){
            operation(1, -(x / y), x, y, ans);
        }else{
            operation(2, -(y / x), x, y, ans);
        }
    }

    // (0,g)->(g,0)
    if(y != 0){
        operation(1, 1, x, y, ans);
        operation(2, -1, x, y, ans);
    }

    return ans;
}

int main(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    if(gcd(a, b) != gcd(c, d)){
        cout << -1 << endl;
        return 0;
    }

    auto ans1 = normalize(a, b), ans2 = normalize(c, d);
    while(ans2.size()){
        Pll p = ans2.back(); ans2.pop_back();
        p.second *= -1;
        ans1.push_back(p);
    }

    ll x = a, y = b;
    cout << ans1.size() << endl;
    for(Pll p: ans1){
        cout << p.first << ' ' << p.second << endl;
        if(p.first == 1){
            x += y * p.second;
        }else{
            y += x * p.second;
        }
    }
    assert(x == c && y == d);

    return 0;
}
0