結果

問題 No.2104 Multiply-Add
ユーザー SumitacchanSumitacchan
提出日時 2022-08-28 18:50:04
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,790 bytes
コンパイル時間 2,324 ms
コンパイル使用メモリ 205,292 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-15 16:22:46
合計ジャッジ時間 3,480 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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