結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー tarakojo1019
提出日時 2021-04-25 15:37:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,699 bytes
コンパイル時間 1,156 ms
コンパイル使用メモリ 116,556 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-04 09:28:04
合計ジャッジ時間 1,798 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

//#define ENVIRONMENT_LINKED_ACL

#ifdef ENVIRONMENT_LINKED_ACL
#include <atcoder/convolution>
#include <atcoder/lazysegtree>
#include <atcoder/segtree.hpp>
#endif

//#define ENVIRONMENT_LINKED_BOOST

#ifdef ENVIRONMENT_LINKED_BOOST
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#endif

using namespace std;
using uint = unsigned int;
using ll   = long long;
using ull  = unsigned long long;
#define REP(i, a, b)    for (ll i = a; i < b; ++i)
#define REPREV(i, a, b) for (ll i = a; i > b; --i)

const int _ = []() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    return 0;
}();

template <typename value_t>
void resize(value_t& v, const value_t& val) { v = val; }
template <typename vec_t, typename value_t, typename... arg_t>
void resize(std::vector<vec_t>& v, const value_t& val, int size, arg_t... arg) {
    v.resize(size);
    for (auto& c : v) resize(c, val, arg...);
}

template <typename A, typename B>
void chmin(A& a, const B& b) {
    a = min(a, static_cast<A>(b));
};
template <typename A, typename B>
void chmax(A& a, const B& b) {
    a = max(a, static_cast<A>(b));
};

//最大公約数
template <typename T>
T gcd(T a, T b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
//最小公倍数
template <typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

//拡張ユークリッドの互除法。戻り値は最大公約数、x,yはax+by=gcd(a,b)を満たす組の一つ
template <typename T>
T gcdext(T a, T b, T& x, T& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    T g = gcdext(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

template <typename T>
T modinv(T v, T mod) {
    T x, y;
    gcdext(v, mod, x, y);
    return (x % mod + mod) % mod;
}

//x == v[i].first (mod v[i].second) を満たす最小のxを求める。mは互いに素
template <typename T>
T garner(const std::vector<std::pair<T, T>>& v) {
    int n    = v.size();
    T m_prod = 1;
    T x      = v[0].first % v[0].second;
    for (int i = 1; i < n; ++i) {
        m_prod *= v[i - 1].second;
        T t = ((v[i].first - x) * modinv<T>(m_prod, v[i].second)) % v[i].second;
        if (t < 0) t += v[i].second;
        x += t * m_prod;
    }
    return x;
}

//x == r[i] (mod m[i]) を満たす最小のx mod (mod)を求める。mは互いに素
template <typename T>
T garner(const std::vector<std::pair<T, T>>& v, T mod) {
    int n    = v.size();
    T m_prod = 1;
    T x      = ((v[0].first % v[0].second) % mod + mod) % mod;
    for (int i = 1; i < n; ++i) {
        T tmp = 1;
        for (int j = 0; j < i; ++j) {
            tmp *= v[j].second;
            tmp %= v[i].second;
        }
        tmp = modinv<T>(tmp, v[i].second);
        m_prod *= v[i - 1].second;
        m_prod %= mod;
        x += (v[i].first - x) * tmp % mod * m_prod % mod;
        x = ((x % mod) + mod) % mod;
    }
    return x;
}

int main() {
    vector<pair<ll, ll>> v(3);
    REP(i, 0, 3) {
        cin >> v[i].first >> v[i].second;
    }
    REP(i, 0, 3) {
        REP(j, i + 1, 3) {
            ll g = gcd(v[i].second, v[j].second);
            if ((v[i].first - v[j].first) % g != 0) {
                cout << -1 << endl;
                return 0;
            }
            ll afilter = gcd(g, v[i].second / g);
            ll bfilter = gcd(g, v[j].second / g);
            ll gcur    = g;
            ll a = 1, b = 1;
            while (true) {
                ll tmp = gcd(afilter, gcur);
                if (tmp == 1) break;
                a *= tmp;
                gcur /= tmp;
            }
            while (true) {
                ll tmp = gcd(bfilter, gcur);
                if (tmp == 1) break;
                b *= tmp;
                gcur /= tmp;
            }
            ll na       = v[i].second / lcm(a, g) * a * gcur;
            ll nb       = v[j].second / lcm(b, g) * b;
            v[i].second = na;
            v[j].second = nb;
            v[i].first %= na;
            v[j].first %= nb;
        }
    }
    auto ret = garner(v);
    if (ret == 0) {
        ll ans = lcm(v[0].second, lcm(v[1].second, v[2].second));
        cout << ans << endl;
    }
    else
        cout << ret << endl;

    return 0;
}
0