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

• 問題: No.186 中華風 (Easy)
• ユーザー: pred
• 提出日時: 2024-01-02 16:29:27
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 6,827 bytes
• コンパイル時間: 2,008 ms
• コンパイル使用メモリ: 202,600 KB
• 最終ジャッジ日時: 2025-02-18 15:52:30
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
other	AC * 23

ソースコード

#include <bits/stdc++.h>
#include <utility>

/* class modint
 * Constructor: modint(mod, val) 
 * Update: 20240101
 */
class modint{
    long long mod;
    static std::map<long long, std::vector<long long>> inverse_table;
public:
    long long val;

    modint(): mod(-1), val(0){}
    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    modint(U m){mod = m; val = 0;}
    template <typename U, typename T, std::enable_if_t<std::is_integral<T>::value && std::is_integral<U>::value, std::nullptr_t> = nullptr>
    modint(U m, T x){mod = m; val = (long long)x % mod; if(val < 0) val += mod;}
    
    long long m() const{return this->mod;}

    modint operator+() const{return *this;}
    modint operator-() const{return modint(mod, this->val == 0 ? 0 : mod - this->val);}

    modint& operator++(){val++; if(val == mod) val = 0; return *this;}
    modint& operator--(){if(val == 0) val = mod; val--; return *this;}
    modint operator++(int){modint temp = *this; ++*this; return temp;}
    modint operator--(int){modint temp = *this; --*this; return temp;}

    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    modint& operator+=(const U &x){return *this += modint(mod, x);}
    modint& operator+=(const modint &x){assert(this->mod == x.mod); val += x.val; if(val >= mod) val -= mod; return *this;}

    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    modint& operator-=(const U &x){return *this -= modint(mod, x);}
    modint& operator-=(const modint &x){assert(this->mod == x.mod); val -= x.val; if(val < 0) val += mod; return *this;}

    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    modint& operator*=(const U &x){return *this *= modint(mod, x);}
    modint& operator*=(const modint &x){assert(this->mod == x.mod); val = val * x.val % mod; return *this;}

    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    modint& operator/=(const U &x){return *this /= modint(mod, x);}
    modint& operator/=(const modint &x){assert(this->mod == x.mod); *this *= x.inverse(); return *this;}

    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    friend modint operator+(const modint &x, const U &y){return modint(x) += y;}
    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    friend modint operator+(const U &x, const modint &y){return modint(y.mod, x) += y;}
    friend modint operator+(const modint &x, const modint &y){return modint(x) += y;}

    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    friend modint operator-(const modint &x, const U &y){return modint(x) -= y;}
    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    friend modint operator-(const U &x, const modint &y){return modint(y.mod, x) -= y;}
    friend modint operator-(const modint &x, const modint &y){return modint(x) -= y;}

    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    friend modint operator*(const modint &x, const U &y){return modint(x) *= y;}
    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    friend modint operator*(const U &x, const modint &y){return modint(y.mod, x) *= y;}
    friend modint operator*(const modint &x, const modint &y){return modint(x) *= y;}

    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    friend modint operator/(const modint &x, const U &y){return modint(x) /= y;}
    template <typename U, std::enable_if_t<std::is_integral<U>::value, std::nullptr_t> = nullptr>
    friend modint operator/(const U &x, const modint &y){return modint(y.mod, x) /= y;}
    friend modint operator/(const modint &x, const modint &y){return modint(x) /= y;}

    //Require: gcd(val, mod) == 1
    friend modint inverse(const modint &x){return x.inverse();}
    //Require: gcd(val, mod) == 1
    modint inverse() const{
        long long r = val, s = mod, a = 1, b = 0, c = 0, d = 1, k;
        while(s){k = r / s, a -= k * c, b -= k * d, r -= k * s, std::swap(a, c), std::swap(b, d), std::swap(r, s);}
        return modint(mod, a);
    }
    modint inverse_from_list() const{
        if(inverse_table[mod].size() > val) return modint(mod, inverse_table[mod][val]);
        else return this->inverse();
    }

    static void make_inverse_list(long long mod, long long max_base){
        assert(max_base > 0);
        auto &v = inverse_table[mod];
        if(v.size() > max_base) return;
        int i = (v.size() > 2 ? v.size() : 2);
        v.resize(max_base + 1, 0);
        v[1] = 1;
        for(; i <= max_base; i++) v[i] = mod - v[mod % i] * (mod / i) % mod;
        return;
    }

    friend modint power(const modint &x, long long exp){return x.power(exp);}
    modint power(long long exp) const{
        modint res(mod, 1), temp(mod, val);
        while(exp){if(exp & 1) res *= val; temp *= temp; exp >>= 1;}
        return res;
    }

    friend bool operator==(const modint &x, const modint &y){return (x.val == y.val) && (x.mod == y.mod);}
    friend bool operator!=(const modint &x, const modint &y){return !(x == y);}

    friend std::istream& operator>>(std::istream &is, modint &x){is >> x.val >> x.mod; return is;}
    friend std::ostream& operator<<(std::ostream &os, const modint &x){os << x.val; return os;}
};

std::map<long long, std::vector<long long>> modint::inverse_table;

/* Chinese Remainder Theorem
 * verified by yukicoder #186
 * Update: 20240102
 */
modint crt(std::vector<modint> vec){
    modint res = vec[0];

    auto extgcd = [](long long r, long long s) -> std::tuple<long long, long long, long long> {
        bool rev = false;
        if(s < r){ std::swap(r, s); rev = true;}
        long long a = 1, b = 0, c = 0, d = 1, k;
        while(s){k = r / s; a -= k * c; b -= k * d; r -= k * s; std::swap(a, c); std::swap(b, d); std::swap(r, s);}
        if(rev) return std::make_tuple(b, a, r);
        else return std::make_tuple(a, b, r);
    };

    for(int i = 1; i < vec.size(); i++){
        auto [rx, ry, g] = extgcd(res.m(), vec[i].m());
        if((res.val - vec[i].val) % g != 0) return modint();
        long long l = vec[i].m() / g;
        res = modint(res.m() * l, res.val + ((vec[i].val - res.val) / g) % l * rx % l * res.m());
    }
    return res;
}

int main(){
    std::vector<modint> v(3);
    for(auto &vi: v) std::cin >> vi;
    auto res = crt(v);
    if(res.m() == -1) std::cout << -1 << "\n";
    else if(res.val == 0) std::cout << res.m() << "\n";
    else std::cout << res.val << "\n";
}