結果
| 問題 |
No.187 中華風 (Hard)
|
| コンテスト | |
| ユーザー |
 drken1215
|
| 提出日時 | 2025-08-11 19:06:46 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 143 ms / 3,000 ms |
| コード長 | 9,908 bytes |
| コンパイル時間 | 3,388 ms |
| コンパイル使用メモリ | 286,404 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-08-11 19:06:55 |
| 合計ジャッジ時間 | 6,687 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 25 |
ソースコード
//
// 中国剰余定理
//
// 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>
bool preGarner(vector<T_VAL> &b, vector<T_VAL> &m) {
assert(b.size() == m.size());
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 false;
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];
}
}
vector<T_VAL> b2, m2;
for (int i = 0; i < (int)b.size(); i++) {
if (m[i] == 1) continue;
b2.emplace_back(b[i]), m2.emplace_back(m[i]);
}
b = b2, m = m2;
return true;
}
// 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() {
const int MOD = 1000000007;
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;
}
if (!preGarner(b, m)) cout << -1 << endl;
else if (!exist_non_zero) {
long long lcm = 1;
for (auto mi : m) lcm = lcm * mi % MOD;
cout << lcm << endl;
} else cout << Garner(b, m, MOD) << endl;
}
int main() {
yukicoder_0187();
}