#977533 (C++17) No.186 中華風 (Easy)

提出ソース
結果

問題	No.186 中華風 (Easy)
ユーザー	ruthen71
提出日時	2024-04-26 20:53:09
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	14,068 bytes
コンパイル時間	2,030 ms
コンパイル使用メモリ	152,708 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-14 11:51:25
合計ジャッジ時間	2,962 ms
ジャッジサーバーID （参考情報）	judge1 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

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

raw source code
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#ifdef RUTHEN_LOCAL
#include <debug.hpp>
#else
#define show(x) true
#endif

// type definition
using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using f32 = float;
using f64 = double;
using f128 = long double;
template <class T> using pque = std::priority_queue<T>;
template <class T> using pqueg = std::priority_queue<T, std::vector<T>, std::greater<T>>;

// overload
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define overload2(_1, _2, name, ...) name

// for loop
#define REP1(a) for (long long _ = 0; _ < (a); _++)
#define REP2(i, a) for (long long i = 0; i < (a); i++)
#define REP3(i, a, b) for (long long i = (a); i < (b); i++)
#define REP4(i, a, b, c) for (long long i = (a); i < (b); i += (c))
#define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define RREP1(a) for (long long _ = (a)-1; _ >= 0; _--)
#define RREP2(i, a) for (long long i = (a)-1; i >= 0; i--)
#define RREP3(i, a, b) for (long long i = (b)-1; i >= (a); i--)
#define RREP(...) overload3(__VA_ARGS__, RREP3, RREP2, RREP1)(__VA_ARGS__)
#define FORE1(x, a) for (auto&& x : a)
#define FORE2(x, y, a) for (auto&& [x, y] : a)
#define FORE3(x, y, z, a) for (auto&& [x, y, z] : a)
#define FORE(...) overload4(__VA_ARGS__, FORE3, FORE2, FORE1)(__VA_ARGS__)
#define FORSUB(t, s) for (long long t = (s); t; t = (t - 1) & (s))

// function
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(a) std::sort((a).begin(), (a).end())
#define RSORT(a) std::sort((a).rbegin(), (a).rend())
#define REV(a) std::reverse((a).begin(), (a).end())
#define UNIQUE(a)                      \
    std::sort((a).begin(), (a).end()); \
    (a).erase(std::unique((a).begin(), (a).end()), (a).end())
#define LEN(a) (int)((a).size())
#define MIN(a) *std::min_element((a).begin(), (a).end())
#define MAX(a) *std::max_element((a).begin(), (a).end())
#define SUM1(a) std::accumulate((a).begin(), (a).end(), 0LL)
#define SUM2(a, x) std::accumulate((a).begin(), (a).end(), (x))
#define SUM(...) overload2(__VA_ARGS__, SUM2, SUM1)(__VA_ARGS__)
#define LB(a, x) std::distance((a).begin(), std::lower_bound((a).begin(), (a).end(), (x)))
#define UB(a, x) std::distance((a).begin(), std::upper_bound((a).begin(), (a).end(), (x)))
template <class T, class U> inline bool chmin(T& a, const U& b) { return (a > T(b) ? a = b, 1 : 0); }
template <class T, class U> inline bool chmax(T& a, const U& b) { return (a < T(b) ? a = b, 1 : 0); }
template <class T, class S> inline T floor(const T x, const S y) {
    assert(y);
    return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));
}
template <class T, class S> inline T ceil(const T x, const S y) {
    assert(y);
    return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y));
}
template <class T, class S> std::pair<T, T> inline divmod(const T x, const S y) {
    T q = floor(x, y);
    return {q, x - q * y};
}
// 10 ^ n
constexpr long long TEN(int n) { return (n == 0) ? 1 : 10LL * TEN(n - 1); }
// 1 + 2 + ... + n
#define TRI1(n) ((n) * ((n) + 1LL) / 2)
// l + (l + 1) + ... + r
#define TRI2(l, r) (((l) + (r)) * ((r) - (l) + 1LL) / 2)
#define TRI(...) overload2(__VA_ARGS__, TRI2, TRI1)(__VA_ARGS__)

// bit operation
// bit[i] (= 0 or 1)
#define IBIT(bit, i) (((bit) >> (i)) & 1)
// (0, 1, 2, 3, 4) -> (0, 1, 3, 7, 15)
#define MASK(n) ((1LL << (n)) - 1)
#define POW2(n) (1LL << (n))
// (0, 1, 2, 3, 4) -> (0, 1, 1, 2, 1)
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(i64 x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(i64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(i64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

// binary search
template <class T, class F> T bin_search(T ok, T ng, F& f) {
    while ((ok > ng ? ok - ng : ng - ok) > 1) {
        T md = (ng + ok) >> 1;
        (f(md) ? ok : ng) = md;
    }
    return ok;
}
template <class T, class F> T bin_search_real(T ok, T ng, F& f, const int iter = 100) {
    for (int _ = 0; _ < iter; _++) {
        T md = (ng + ok) / 2;
        (f(md) ? ok : ng) = md;
    }
    return ok;
}

// rotate matrix counterclockwise by pi / 2
template <class T> void rot(std::vector<std::vector<T>>& a) {
    if ((int)(a.size()) == 0) return;
    if ((int)(a[0].size()) == 0) return;
    int n = (int)(a.size()), m = (int)(a[0].size());
    std::vector res(m, std::vector<T>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            res[m - 1 - j][i] = a[i][j];
        }
    }
    a.swap(res);
}

// const value
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

// infinity
template <class T> constexpr T INF = 0;
template <> constexpr int INF<int> = 1'000'000'000;                 // 1e9
template <> constexpr i64 INF<i64> = i64(INF<int>) * INF<int> * 2;  // 2e18
template <> constexpr u32 INF<u32> = INF<int>;                      // 1e9
template <> constexpr u64 INF<u64> = INF<i64>;                      // 2e18
template <> constexpr f32 INF<f32> = INF<i64>;                      // 2e18
template <> constexpr f64 INF<f64> = INF<i64>;                      // 2e18
template <> constexpr f128 INF<f128> = INF<i64>;                    // 2e18

// input
template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto&& i : v) is >> i;
    return is;
}
template <class... T> void in(T&... a) { (std::cin >> ... >> a); }
void scan() {}
template <class Head, class... Tail> void scan(Head& head, Tail&... tail) {
    in(head);
    scan(tail...);
}

// definition & input
#define INT(...)     \
    int __VA_ARGS__; \
    scan(__VA_ARGS__)
#define I64(...)     \
    i64 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define U32(...)     \
    u32 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define U64(...)     \
    u64 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define F32(...)     \
    f32 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define F64(...)     \
    f64 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define F128(...)     \
    f128 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define STR(...)             \
    std::string __VA_ARGS__; \
    scan(__VA_ARGS__)
#define CHR(...)      \
    char __VA_ARGS__; \
    scan(__VA_ARGS__)
#define VEC(type, name, size)     \
    std::vector<type> name(size); \
    scan(name)
#define VEC2(type, name1, name2, size)          \
    std::vector<type> name1(size), name2(size); \
    for (int i = 0; i < size; i++) scan(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, size)                \
    std::vector<type> name1(size), name2(size), name3(size); \
    for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, size)                      \
    std::vector<type> name1(size), name2(size), name3(size), name4(size); \
    for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i], name4[i])
#define VV(type, name, h, w)                       \
    std::vector name((h), std::vector<type>((w))); \
    scan(name)

// output
template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    auto n = v.size();
    for (size_t i = 0; i < n; i++) {
        if (i) os << ' ';
        os << v[i];
    }
    return os;
}
template <class... T> void out(const T&... a) { (std::cout << ... << a); }
void print() {
    out('\n');
    // std::cout.flush();
}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {
    out(head);
    if (sizeof...(Tail)) out(' ');
    print(tail...);
}
// for interactive problems
void printflush() {
    out('\n');
    std::cout.flush();
}
template <class Head, class... Tail> void printflush(Head&& head, Tail&&... tail) {
    out(head);
    if (sizeof...(Tail)) out(' ');
    printflush(tail...);
}

// bool output
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void NO(bool t = 1) { YES(!t); }
void No(bool t = 1) { Yes(!t); }
void no(bool t = 1) { yes(!t); }
void POSSIBLE(bool t = 1) { print(t ? "POSSIBLE" : "IMPOSSIBLE"); }
void Possible(bool t = 1) { print(t ? "Possible" : "Impossible"); }
void possible(bool t = 1) { print(t ? "possible" : "impossible"); }
void IMPOSSIBLE(bool t = 1) { POSSIBLE(!t); }
void Impossible(bool t = 1) { Possible(!t); }
void impossible(bool t = 1) { possible(!t); }
void FIRST(bool t = 1) { print(t ? "FIRST" : "SECOND"); }
void First(bool t = 1) { print(t ? "First" : "Second"); }
void first(bool t = 1) { print(t ? "first" : "second"); }
void SECOND(bool t = 1) { FIRST(!t); }
void Second(bool t = 1) { First(!t); }
void second(bool t = 1) { first(!t); }

// I/O speed up
struct SetUpIO {
    SetUpIO() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
        std::cout << std::fixed << std::setprecision(15);
    }
} set_up_io;

// find (x, y) s.t. ax + by = gcd(a, b)
// a, b >= 0
// return {x, y, gcd(a, b)}
template <class T> std::tuple<T, T, T> extended_gcd(T a, T b) {
    if (b == 0) return {1, 0, a};
    auto [y, x, g] = extended_gcd(b, a % b);
    return {x, y - (a / b) * x, g};
}

// Reference: https://ja.wikipedia.org/wiki/ベズーの等式
// ax + by = c を解く (a, b >= 0)
// return {x, y, gcd(a, b), has_solution}
// 解が存在するとき
// (1) a = 0, b = 0, c = 0 のとき
//   x, y は任意
//   {0, 0, gcd(a, b) = 0, 1} を返す
// (2) a = 0, c が b の倍数のとき
//   x は任意, y = c / b
//   {0, c / b, gcd(a, b) = b, 1} を返す
// (3) b = 0, c が a の倍数のとき
//   y は任意, x = c / b
//   {c / a, 0, gcd(a, b) = a, 1} を返す
// (4) a > 0, b > 0, c % gcd(a, b) = 0 のとき
//   x = x' + k * (b / gcd(a, b)), y = y' - k * (a / gcd(a, b))
//   {x', y', gcd(a, b), 1} を返す
// 解が存在しないとき
// {-1, -1, -1, 0} を返す
template <class T> std::tuple<T, T, T, int> linear_diophantine(T a, T b, T c) {
    assert(a >= 0 and b >= 0);
    if (a == 0 and b == 0) {
        if (c == 0) return {0, 0, 0, 1};
        return {-1, -1, -1, 0};
    }
    if (a == 0) {
        // by = c
        if (c % b == 0) return {0, c / b, b, 1};
        return {-1, -1, -1, 0};
    }
    if (b == 0) {
        // ax = c
        if (c % a == 0) return {c / a, 0, a, 1};
        return {-1, -1, -1, 0};
    }
    // as + bt = gcd(a, b) から ax + by = c を求める
    // x = s * (c / gcd(a, b)), y = t * (c / gcd(a, b)) よりも x, y が小さくなる?
    // c = c' + a * dx + b * dy となるように c' を求める
    // (a, b は gcd(a, b) の倍数なので c' は gcd(a, b) の倍数)
    // x = dx + s * (c' / gcd(a, b)), y = dy + t * (c' / gcd(a, b)) が解となる
    // ax + by = a * dx + b * dy + (as + bt) * (c' / gcd(a, b)) = a * dx + b * dy + c' = c
    auto [s, t, g] = extended_gcd(a, b);
    if (c % g != 0) return {-1, -1, -1, 0};
    T dx = c / a;
    c -= dx * a;
    T dy = c / b;
    c -= dy * b;
    T x = dx + s * (c / g);
    T y = dy + t * (c / g);
    return {x, y, g, 1};
}

// 線形合同式 ax = b (mod m) を解く (m > 0)
// 解が存在する場合 x = x' (mod h) となるときの最小の x' と h を返す
// 解が存在しない場合 {-1, -1} を返す
template <class T> std::pair<T, T> linear_congruence(T a, T b, T m) {
    assert(m > 0);
    a = (a % m + m) % m;
    b = (b % m + m) % m;
    // ax = b (mod m) <=> ax + my = b となる (x, y) が存在
    auto [x, y, g, is_ok] = linear_diophantine(a, m, b);
    if (!is_ok) return {-1, -1};
    T h = m / g;
    x = (x % h + h) % h;
    return {x, h};
}

// (rem, mod)
std::pair<long long, long long> chinese_remainder_theorem(const std::vector<long long>& r, const std::vector<long long>& m) {
    assert(r.size() == m.size());
    const int n = (int)(r.size());
    long long r0 = 0, m0 = 1;
    for (int i = 0; i < n; i++) {
        assert(m[i] >= 1);
        long long r1 = r[i] % m[i], m1 = m[i];
        if (r1 < 0) r1 += m[i];
        if (m0 < m1) {
            std::swap(r0, r1);
            std::swap(m0, m1);
        }
        // m0 > m1
        if (m0 % m1 == 0) {
            if (r0 % m1 != r1) return {0, 0};
            continue;
        }
        // (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1))
        // r2 % m0 = r0
        // -> r2 = r0 + x * m0
        // r2 % m1 = r1
        // -> (r0 + x * m0) % m1 = r1
        // -> x * m0 = r1 - r0 (mod m1)
        auto [x, h] = linear_congruence(m0, r1 - r0, m1);
        if (x == -1 and h == -1) return {0, 0};
        r0 += x * m0;
        m0 *= h;
        r0 %= m0;
        if (r0 < 0) r0 += m0;
    }
    return {r0, m0};
}

using namespace std;

void solve() {
    VEC2(i64, X, Y, 3);
    auto [r, m] = chinese_remainder_theorem(X, Y);
    if (m == 0) {
        print(-1);
    } else {
        print(r);
    }
    return;
}

int main() {
    solve();
    return 0;
}
yukicoder

結果

テストケース

ソースコード
