結果

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

ソースコード

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;
}

//中国剰余定理 x % mod1 == v1 % mod1, x % mod2 == v2 % mod2 と同値な合同式 x % lcm(mod1, mod2) == r % lcm の(r, lcm)を求める。
//解が存在する条件は、v1 % gcd(mod1, mod2) == v2 % gcd(mod1, mod2)
template <typename T>
std::pair<T, T> CRT(T v1, T mod1, T v2, T mod2) {
    if (mod1 <= 0 || mod2 <= 0) return {0, 0};
    T p, q;
    T g = gcdext(mod1, mod2, p, q);
    if ((v2 - v1) % g != 0) return {0, 0};
    T s   = (v2 - v1) / g;
    T mod = lcm(mod1, mod2);
    T r   = v1 + s * mod1 % mod * p % mod;
    return {(r % mod + mod) % mod, mod};
}
template <typename T>
std::pair<T, T> CRT(std::vector<std::pair<T, T>>& v) {
    pair<T, T> ans = {0, 1};
    for (auto p : v) ans = CRT(ans.first, ans.second, p.first, p.second);
    return ans;
}

int main() {
    vector<pair<ll, ll>> v(3);
    REP(i, 0, 3) {
        cin >> v[i].first >> v[i].second;
    }
    auto ret = CRT<ll>(v);
    if (ret.second == 0)
        cout << -1 << endl;
    else
        cout << ret.first << endl;
    return 0;
}
0