結果
問題 |
No.187 中華風 (Hard)
|
ユーザー |
![]() |
提出日時 | 2025-08-11 18:55:26 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 9,729 bytes |
コンパイル時間 | 3,164 ms |
コンパイル使用メモリ | 282,432 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-11 18:55:33 |
合計ジャッジ時間 | 6,560 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 RE * 4 |
ソースコード
// // 中国剰余定理 // // cf. // 中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ // https://qiita.com/drken/items/ae02240cd1f8edfc86fd // // verified // yukicoder 0187 中華風 (Hard) // https://yukicoder.me/problems/no/187 // /* x ≡ b[i] (mod. m[i]) を満たす最小の正の整数を x として、x % MOD の値を求める */ #include <bits/stdc++.h> using namespace std; #define REP(i, a) for (long long i = 0; i < (long long)(a); i++) #define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++) #define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i) #define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i) #define EB emplace_back #define PB push_back #define MP make_pair #define MT make_tuple #define FI first #define SE second #define ALL(x) x.begin(), x.end() #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) { return s << '<' << P.first << ", " << P.second << '>'; } template<class T> ostream& operator << (ostream &s, array<T, 3> P) { return s << '<' << P[0] << ", " << P[1] << ", " << P[2] << '>'; } template<class T> ostream& operator << (ostream &s, array<T, 4> P) { return s << '<' << P[0] << ", " << P[1] << ", " << P[2] << ", " << P[3] << '>'; } template<class T> ostream& operator << (ostream &s, vector<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, deque<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template<class T> ostream& operator << (ostream &s, set<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T> ostream& operator << (ostream &s, multiset<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T> ostream& operator << (ostream &s, unordered_set<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } template<class T1, class T2> ostream& operator << (ostream &s, unordered_map<T1,T2> P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } // safe mod template<class T_VAL, class T_MOD> constexpr T_VAL safe_mod(T_VAL a, T_MOD m) { assert(m > 0); a %= m; if (a < 0) a += m; return a; } // mod pow template<class T_VAL, class T_MOD> constexpr T_VAL mod_pow(T_VAL a, T_VAL n, T_MOD m) { assert(m > 0); T_VAL res = 1; while (n > 0) { if (n % 2 == 1) res = res * a % m; a = a * a % m; n >>= 1; } return res; } // mod inv template<class T_VAL, class T_MOD> constexpr T_VAL mod_inv(T_VAL a, T_MOD m) { assert(m > 0); T_VAL b = m, u = 1, v = 0; while (b > 0) { T_VAL t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } u %= m; if (u < 0) u += m; return u; } // dynamic modint struct DynamicModint { using mint = DynamicModint; // static menber static int MOD; // inner value unsigned int val; // constructor DynamicModint() : val(0) { } template<std::signed_integral T> DynamicModint(T v) { long long tmp = (long long)(v % (long long)(get_umod())); if (tmp < 0) tmp += get_umod(); val = (unsigned int)(tmp); } template<std::unsigned_integral T> DynamicModint(T v) { val = (unsigned int)(v % get_umod()); } long long get() const { return val; } static int get_mod() { return MOD; } static unsigned int get_umod() { return MOD; } static void set_mod(int mod) { MOD = mod; } // arithmetic operators mint operator + () const { return mint(*this); } mint operator - () const { return mint() - mint(*this); } mint operator + (const mint &r) const { return mint(*this) += r; } mint operator - (const mint &r) const { return mint(*this) -= r; } mint operator * (const mint &r) const { return mint(*this) *= r; } mint operator / (const mint &r) const { return mint(*this) /= r; } mint& operator += (const mint &r) { val += r.val; if (val >= get_umod()) val -= get_umod(); return *this; } mint& operator -= (const mint &r) { val -= r.val; if (val >= get_umod()) val += get_umod(); return *this; } mint& operator *= (const mint &r) { unsigned long long tmp = val; tmp *= r.val; val = (unsigned int)(tmp % get_umod()); return *this; } mint& operator /= (const mint &r) { return *this = *this * r.inv(); } mint pow(long long n) const { assert(n >= 0); mint res(1), mul(*this); while (n) { if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } mint inv() const { assert(val); return mod_inv((long long)(val), get_umod()); } // other operators bool operator == (const mint &r) const { return this->val == r.val; } bool operator != (const mint &r) const { return this->val != r.val; } bool operator < (const mint &r) const { return this->val < r.val; } bool operator > (const mint &r) const { return this->val > r.val; } bool operator <= (const mint &r) const { return this->val <= r.val; } bool operator >= (const mint &r) const { return this->val >= r.val; } mint& operator ++ () { ++val; if (val == get_umod()) val = 0; return *this; } mint& operator -- () { if (val == 0) val = get_umod(); --val; return *this; } mint operator ++ (int) { mint res = *this; ++*this; return res; } mint operator -- (int) { mint res = *this; --*this; return res; } friend istream& operator >> (istream &is, mint &x) { long long tmp = 1; is >> tmp; tmp = tmp % (long long)(get_umod()); if (tmp < 0) tmp += get_umod(); x.val = (unsigned int)(tmp); return is; } friend ostream& operator << (ostream &os, const mint &x) { return os << x.val; } friend mint pow(const mint &r, long long n) { return r.pow(n); } friend mint inv(const mint &r) { return r.inv(); } }; int DynamicModint::MOD; // Garner's algorithm // if m is not coprime, call this function first template<class T_VAL, class T_MOD> T_VAL preGarner(vector<T_VAL> &b, vector<T_VAL> &m, T_MOD MOD) { T_VAL res = 1; for (int i = 0; i < (int)b.size(); ++i) { for (int j = 0; j < i; ++j) { T_VAL g = gcd(m[i], m[j]); if ((b[i] - b[j]) % g != 0) return -1; m[i] /= g, m[j] /= g; T_VAL gi = gcd(m[i], g), gj = g/gi; do { g = gcd(gi, gj); gi *= g, gj /= g; } while (g != 1); m[i] *= gi, m[j] *= gj; b[i] %= m[i], b[j] %= m[j]; } } for (int i = 0; i < (int)b.size(); ++i) (res *= m[i]) %= MOD; return res; } // find x (%MOD), LCM (%MOD) (m must be coprime) // for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (mod. m[k])" // coeffs[k] = m[0]m[1]...m[k-1] // constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2] template<class T_VAL> T_VAL Garner(vector<T_VAL> b, vector<T_VAL> m) { assert(b.size() == m.size()); using mint = DynamicModint; int num = (int)m.size(); T_VAL res = 0, lcm = 1; vector<long long> coeffs(num, 1), constants(num, 0); for (int k = 0; k < num; k++) { mint::set_mod(m[k]); T_VAL t = ((mint(b[k]) - constants[k]) / coeffs[k]).val; for (int i = k + 1; i < num; i++) { constants[i] = safe_mod(constants[i] + t * coeffs[i], m[i]); coeffs[i] = safe_mod(coeffs[i] * m[k], m[i]); } res += t * lcm; lcm *= m[k]; } return res; } template<class T_VAL, class T_MOD> T_VAL Garner(vector<T_VAL> b, vector<T_VAL> m, T_MOD MOD) { assert(b.size() == m.size()); assert(MOD > 0); using mint = DynamicModint; int num = (int)m.size(); T_VAL res = 0, lcm = 1; vector<long long> coeffs(num, 1), constants(num, 0); for (int k = 0; k < num; k++) { mint::set_mod(m[k]); T_VAL t = ((mint(b[k]) - constants[k]) / coeffs[k]).val; for (int i = k + 1; i < num; i++) { constants[i] = safe_mod(constants[i] + t * coeffs[i], m[i]); coeffs[i] = safe_mod(coeffs[i] * m[k], m[i]); } res = safe_mod(res + t * lcm, MOD); lcm = safe_mod(lcm * m[k], MOD); } return res; } //------------------------------// // Examples //------------------------------// // yukicoder 0187 中華風 (Hard) void yukicoder_0187() { int N; cin >> N; vector<long long> b(N), m(N); bool exist_non_zero = false; for (int i = 0; i < N; ++i) { cin >> b[i] >> m[i]; if (b[i]) exist_non_zero = true; } const int MOD = 1000000007; long long lcm = preGarner(b, m, MOD); if (!exist_non_zero) cout << lcm << endl; else if (lcm == -1) cout << -1 << endl; else cout << Garner(b, m, MOD) << endl; } int main() { yukicoder_0187(); }