結果

問題 No.186 中華風 (Easy)
ユーザー hedwig100hedwig100
提出日時 2022-09-22 12:50:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 5,187 bytes
コンパイル時間 2,195 ms
コンパイル使用メモリ 203,560 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-23 20:30:09
合計ジャッジ時間 2,973 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_
void debug_out() {
    cerr << "\033[0m" << endl;
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H << ',';
    debug_out(T...);
}
#define debug(...) cerr << "\033[1;36m" << __func__ << ":L" << __LINE__ << " " << #__VA_ARGS__ << ":", debug_out(__VA_ARGS__)
#define dump(x) cerr << __func__ << ":L" << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define irep(i, n) for (int i = (int)(n)-1; i >= 0; --i)

using ll  = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

constexpr int INF        = 1000'000'000;
constexpr long long HINF = 4000'000'000000'000'000;
constexpr long long MOD  = 1000000007; // = 998244353;
constexpr double EPS     = 1e-4;
constexpr double PI      = 3.14159265358979;

#pragma region Macros
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << '[';
    for (auto &e : v) {
        os << e << ',';
    }
    os << ']';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st) {
    os << '{';
    for (auto itr = st.begin(); itr != st.end(); itr++) {
        os << *itr << ',';
    }
    os << '}';
    return os;
}
template <typename K, typename V>
ostream &operator<<(ostream &os, const map<K, V> &mp) {
    os << '{';
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        os << itr->first << ": " << itr->second << ',';
    }
    os << '}';
    return os;
}

void yn(bool cond, string Yes = "Yes", string No = "No") {
    cout << (cond ? Yes : No) << '\n';
}

template <typename T>
bool chmax(T &x, const T &y) {
    return (x < y) ? (x = y, true) : false;
}

template <typename T>
bool chmin(T &x, const T &y) {
    return (x > y) ? (x = y, true) : false;
}

#pragma endregion

// gcd
// 非負整数a,bの最大公約数を求める.
// 制約: a,b >= 0
// 計算量: O(logmax(a,b))
template <typename T>
T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }

// lcm
// 非負整数a,bの最小公倍数を求める.
// 制約: a,b >= 0
// 計算量: O(logmax(a,b))
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ext_gcd
// 拡張Euclidの互除法で非負整数a,bに対してax + by = gcd(a,b)を満たす整数x,yを求める.
// 出力される値は xy != 0 ならば |x| <= b,|y| <= a を満たす.
// 制約: a,b >= 0
// 計算量: O(logmax(a,b))
template <typename T>
pair<T, T> ext_gcd(T a, T b) {
    if (b == 0) {
        return make_pair(1, 0);
    }
    auto [x, y] = ext_gcd(b, a % b);
    return make_pair(y, x - a / b * y);
}

// pow_mod
// x^k mod mを計算する.
// 計算量: O(logk)
template <typename T>
T pow_mod(T x, long long k, int m) {
    T ret = T(1);
    while (k > 0) {
        if (k & 1) {
            ret *= x;
            ret %= m;
        }
        k >>= 1;
        x *= x;
        x %= m;
    }
    return ret;
}

// inv_mod
// ax = 1 (mod m) なるx (0 <= x < m)が存在するならば
// それを返し, 存在しなければ-1を返す.
// 計算量: O(log|max(a,m)|)
template <typename T>
T inv_mod(T a, T m) {
    auto [x, y] = ext_gcd(a, m);
    T g         = a * x + m * y;
    if (g != 1) return -1;
    return (m + x % m) % m;
}

// linear_congruence
// forall i,A_i x = B_i mod M_i <=> x = b mod m
// とかけるときに(b,m)の組を返す. ただし(0 <= b < m)をみたす. このように書けない時は(-1,-1)を返す.
// 計算量: O(nlogmax|M_i|),nは式の数
template <typename T>
pair<T, T> linear_congruence(const vector<T> &A, const vector<T> &B, const vector<T> &M) {
    T x = 0, m = 1;
    for (int i = 0; i < (int)A.size(); i++) {
        T a = A[i] * m, b = B[i] - A[i] * x, d = gcd(M[i], a);
        if (b % d != 0) return make_pair(-1, -1);
        T t = b / d * inv_mod(a / d, M[i] / d) % (M[i] / d);
        x += m * t;
        m *= M[i] / d;
    }
    return make_pair((m + x % m) % m, m);
}

// garner
// forall i, x = B_i mod M_i <=> x = b mod m
// とかけるときに(b,m)の組を返す. ただし(0 <= b < m)をみたす. このように書けない時は(-1,-1)を返す.
// 計算量: O(nlogmax|M_i|),nは式の数
template <typename T>
pair<T, T> garner(const vector<T> &R, const vector<T> &M) {
    vector<T> A(R.size(), 1);
    return linear_congruence(A, R, M);
}

// aのk乗根を求める
long long root_int(long long a, int k) {
    if (k == 0) return 0;
    long long x = pow(a, (double)1.0 / k);
    while (pow(x, k) > a)
        x--;
    while (pow(x + 1, k) <= a)
        x++;
    return x;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    vector<ll> X(3), Y(3);
    rep(i, 3) cin >> X[i] >> Y[i];
    auto [x, m] = garner(X, Y);
    if (x == 0)
        cout << m << '\n';
    else
        cout << x << '\n';
    return 0;
}
0