結果
| 問題 | No.187 中華風 (Hard) |
| コンテスト | |
| ユーザー |
 2251799813685248
|
| 提出日時 | 2026-07-10 22:42:15 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 103 ms / 3,000 ms |
| コード長 | 14,002 bytes |
| 記録 | |
| コンパイル時間 | 2,655 ms |
| コンパイル使用メモリ | 236,968 KB |
| 実行使用メモリ | 5,888 KB |
| 最終ジャッジ日時 | 2026-07-10 22:42:27 |
| 合計ジャッジ時間 | 5,505 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 25 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>
#include <random>
#include <bitset>
// #include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using ll = long long;
using lll = __int128_t;
using ull = unsigned long long;
#ifdef BOOST_VERSION
using bll = boost::multiprecision::cpp_int;
#endif
using ld = long double;
using pii = array<int,2>;
using pll = array<ll,2>;
using plll = array<lll,2>;
#define vall(A) A.begin(), A.end()
template<typename T> ostream& operator<<(ostream& os, const array<T, 2>& p) {os << p[0] << " " << p[1]; return os;}
inline void print(){cout << "\n";}
inline void printflush(){cout << endl;}
template<typename T, typename... U> inline void print(const T& obj1, const U&... obj2){cout << (obj1) << (sizeof...(U) == 0 ? "" : " "); print(obj2...);}
template<typename T, typename... U> inline void printflush(const T& obj1, const U&... obj2){cout << (obj1) << (sizeof...(U) == 0 ? "" : " "); printflush(obj2...);}
template<typename T> inline void vin(T& A){for (int i = 0, sz = A.size(); i < sz; i++){cin >> A[i];}}
template<typename T> inline void vout(const T& A){if (A.size() == 0ull){print();} for (int i = 0, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}}
template<typename T> inline void vout2d(const T& A){if (A.size() == 0ull){print();} for (int i = 0, H = A.size(); i < H; i++){vout(A[i]);}}
template<typename T> inline void adjvin(T& A){for (int i = 1, sz = A.size(); i < sz; i++){cin >> A[i];}}
template<typename T> inline void adjvout(const T& A){for (int i = 1, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}}
template<typename T> inline void adjvout2d(const T& A){if (A.size() == 0ull){print();} for (int i = 1, H = A.size(); i < H; i++){adjvout(A[i]);}}
template<typename T> inline bool btest(T K, int i){return K&(1ull<<i);}
#ifndef LEN_DEFINED
#define LEN_DEFINED
template<typename T> inline ll len(T A){return ssize(A);}
#endif
constexpr ll pow2ll[63] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904};
constexpr ll pow10ll[19] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
constexpr ll di[4] = {0,1,0,-1};
constexpr ll di8[8] = {0,1,1,1,0,-1,-1,-1};
constexpr ll dj[4] = {1,0,-1,0};
constexpr ll dj8[8] = {1,1,0,-1,-1,-1,0,1};
#ifndef CRT_HPP_
#define CRT_HPP_
#include <array>
#include <cmath>
#include <cassert>
#include <vector>
#ifndef MATH_FUNCTION_HPP_
#define MATH_FUNCTION_HPP_
#include <array>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ulll = __uint128_t;
#ifdef BOOST_VERSION
using bll = boost::multiprecision::cpp_int;
#endif
/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる
constexpr ll modpow(ll a, ull b, const ll m){
ll t = a%m;
ll ans = (m == 1 ? 0 : 1);
while (b > 0){
if (b&1){
ans = (ans*t)%m;
}
b >>= 1;
t = (t*t)%m;
}
return ans;
}
/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。mはコンパイル時に決定している必要がある
template<ll m> constexpr ll modpow(ll a, ull b){
ll t = a%m;
ll ans = (m == 1 ? 0 : 1);
while (b > 0){
if (b&1){
ans = (ans*t)%m;
}
b >>= 1;
t = (t*t)%m;
}
return ans;
}
/// @brief a^nを返す。bに関して対数時間で計算できる
constexpr ll powll(ll a, ull n){
ll t = a;
ll ans = 1;
while (n > 0){
if (n&1){
ans *= t;
}
n >>= 1;
t *= t;
}
return ans;
}
/// @brief floor(sqrt(N))を返す。1.5×10^19まで対応
constexpr ll isqrt(ull N){
assert(N <= 15000000000000000000ull);
ull ret = sqrt(N);
while (ret*ret > N){
ret--;
}
while ((ret+1)*(ret+1) <= N){
ret++;
}
return ret;
}
#ifdef BOOST_VERSION
/// @brief floor(sqrt(N))を返す。多倍長整数に対応
constexpr bll isqrt_large(bll N){
bll ret = sqrt(N);
while (ret*ret > N){
ret--;
}
while ((ret+1)*(ret+1) <= N){
ret++;
}
return ret;
}
#endif
/// @brief floor(log_a(L))を返す
constexpr ll ilog(ll a, ll L){
__int128_t t = 1;
ll ans = 0;
while (t <= L){
ans++;
t *= a;
}
return ans-1;
}
/// @brief 有理数のfloorを求める。 floor(y/x)
template<typename T> constexpr inline T floor2(T y, T x){
if ((x^y) > 0){
x = x > 0 ? x : -x;
y = y > 0 ? y : -y;
return y/x;
}
else if ((x^y) < 0){
x = x > 0 ? x : -x;
y = y > 0 ? y : -y;
return -((y+x-1)/x);
}
else{
return y/x;
}
}
/// @brief 有理数のceilを求める。 ceil(y/x)
template<typename T> constexpr inline T ceil2(T y, T x){
if ((x^y) > 0){
x = x > 0 ? x : -x;
y = y > 0 ? y : -y;
return (y+x-1)/x;
}
else if ((x^y) < 0){
x = x > 0 ? x : -x;
y = y > 0 ? y : -y;
return -(y/x);
}
else{
return y/x;
}
}
/// @brief 一次不定方程式ax+by=gcd(a,b)の解を1つ見つける
/// @param a `a>=0`である必要がある
/// @param b `b>=0`である必要がある
/// @return {x,y,gcd(a,b)}
template<typename T>
constexpr array<T,3> axby1(T a, T b){
T x = 1, y = 0;
T z = 0, w = 1;
T tmp = 0;
while (b){
T p = a/b, q = a%b;
tmp = x - y * p; x = y; y = tmp;
tmp = z - w * p; z = w; w = tmp;
a = b; b = q;
}
return {x, z, a};
}
/// @brief 1/a mod Mを求める
template<typename T, typename U>
constexpr T inverse_mod(T a, U M){
auto temp = axby1(a,(T)M);
assert(temp[2] == 1);
return (M+temp[0])%M;
}
/// @brief sqrt(a) mod Mを求める。ないなら-1が返される。
template<ll M>
inline constexpr ll cipolla(ll a){
a %= M;
if (M == 2) return a;
if (a == 0) return 0;
ll z = (M-1)/2;
if (modpow<M>(a, z) != 1){return -1;}
int b = 0;
while (modpow<M>((b*b+M-a)%M, z) == 1){
b++;
}
array<ll,2> x{1,0};
array<ll,2> y{b, 1};
ll w = (b*b+M-a)%M;
z++;
while (z){
if (z&1){
ll temp = x[0];
x[0] = x[0]*y[0]%M+x[1]*y[1]%M*w%M;
if (x[0] >= M){x[0] -= M;}
x[1] = temp*y[1]%M+x[1]*y[0]%M;
if (x[1] >= M){x[1] -= M;}
}
ll temp = y[0];
y[0] = y[0]*y[0]%M+y[1]*y[1]%M*w%M;
if (y[0] >= M){y[0] -= M;}
y[1] = 2*temp*y[1]%M;
z >>= 1;
}
return x[0];
}
inline constexpr ll cipolla(ll a, const ll M){
a %= M;
if (M == 2) return a;
if (a == 0) return 0;
ll z = (M-1)/2;
if (modpow(a, z, M) != 1){return -1;}
int b = 0;
while (modpow((b*b+M-a)%M, z, M) == 1){
b++;
}
array<ll,2> x{1,0};
array<ll,2> y{b, 1};
ll w = (b*b+M-a)%M;
z++;
while (z){
if (z&1){
ll temp = x[0];
x[0] = x[0]*y[0]%M+x[1]*y[1]%M*w%M;
if (x[0] >= M){x[0] -= M;}
x[1] = temp*y[1]%M+x[1]*y[0]%M;
if (x[1] >= M){x[1] -= M;}
}
ll temp = y[0];
y[0] = y[0]*y[0]%M+y[1]*y[1]%M*w%M;
if (y[0] >= M){y[0] -= M;}
y[1] = 2*temp*y[1]%M;
z >>= 1;
}
return x[0];
}
/// @brief x以下の最大の2冪を返す。0は0が返る。
constexpr ull lowerpow2(ull x){
if (x == 0){return 0;}
return 1ull<<(63-__builtin_clzll(x));
}
/// @brief x以上の最小の2冪を返す。0は0が返る。
constexpr ull upperpow2(ull x){
if (x == 0){return 0;}
if (x == 1){return 1;}
return 1ull<<(64-__builtin_clzll(x-1));
}
/// @brief xのpopcountを求める
constexpr int popcount(ull x){
return __builtin_popcountll(x);
}
/// @brief xのbit lengthを求める。
constexpr int bit_length(ull x){
if (x == 0){return 0;}
return 64-__builtin_clzll(x);
}
#endif /* MATH_FUNCTION_HPP_ */
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#ifdef BOOST_VERSION
using bll = boost::multiprecision::cpp_int;
#endif
#ifndef LEN_DEFINED
#define LEN_DEFINED
template<typename T> inline ll len(T A){return ssize(A);}
#endif
// Garnerのアルゴリズムで元の数を復元する。すべての法同士が互いに素である必要がある。解のうち最小の非負整数が返る。
template<typename T> constexpr T crt_relatively_prime(const vector<T>& r, const vector<T>& m){
T ans = 0;
int N = len(r);
assert(N == len(m));
vector<T> A(N);
for (int i = 0; i < N; i++){
ll b = r[i]%m[i];
ll cumulative_prod = 1;
for (int k = 0; k < i; k++){
b += m[i]-cumulative_prod%m[i]*A[k]%m[i];
if (b >= m[i]){b -= m[i];}
cumulative_prod *= m[k];
}
A[i] = b*inverse_mod<T>(cumulative_prod, m[i])%m[i];
ans += A[i]*cumulative_prod;
}
return ans;
}
// Garnerのアルゴリズムで元の数を復元する。すべての法同士が互いに素である必要がある。解のうち最小の非負整数%MODが返る。
template<typename T> constexpr T crt_relatively_prime(const vector<T>& r, const vector<T>& m, T MOD){
T ans = 0;
int N = len(r);
assert(N == len(m));
vector<T> A(N);
for (int i = 0; i < N; i++){
ll b = r[i]%m[i];
ll cumulative_prod1 = 1;
ll cumulative_prod2 = 1;
for (int k = 0; k < i; k++){
b += m[i]-cumulative_prod1*A[k]%m[i];
if (b >= m[i]){b -= m[i];}
cumulative_prod1 = cumulative_prod1*m[k]%m[i];
cumulative_prod2 = cumulative_prod2*m[k]%MOD;
}
A[i] = b*inverse_mod<T>(cumulative_prod1, m[i])%m[i];
ans += A[i]*cumulative_prod2%MOD;
if (ans >= MOD){
ans -= MOD;
}
}
return ans;
}
#ifdef BOOST_VERSION
// Garnerのアルゴリズムで元の数を復元する。すべての法同士が互いに素である必要がある。解のうち最小の非負整数が返る。多倍長整数版
constexpr bll crt_relatively_prime_large(const vector<bll>& r, const vector<bll>& m){
bll ans = 0;
int N = len(r);
assert(N == len(m));
vector<bll> A(N);
for (int i = 0; i < N; i++){
bll b = r[i]%m[i];
bll cumulative_prod = 1;
for (int k = 0; k < i; k++){
b += m[i]-cumulative_prod%m[i]*A[k]%m[i];
if (b >= m[i]){b -= m[i];}
cumulative_prod *= m[k];
}
A[i] = b*inverse_mod<bll>(cumulative_prod, m[i])%m[i];
ans += A[i]*cumulative_prod;
}
return ans;
}
#endif
template<typename T> inline constexpr T internal_arrange_mod(T m1, T m2, T g){
g = gcd(g, m2/g);
T temp = m1;
do{
temp /= g;
g = gcd(g, temp);
}while(g > 1);
return temp;
}
// Garnerのアルゴリズムで元の数を復元する。存在しなければ-1が返り、存在するならばありうるもののうち、最小の非負整数が返る。
//modの最小公倍数も求まる。
template<typename T> constexpr array<T, 2> crt(vector<T> r, vector<T> m){
int N = len(r);
assert(N == len(m));
for (int i = 0; i < N-1; i++){
for (int j = i+1; j < N; j++){
T g = gcd(m[i], m[j]);
if ((r[i]-r[j])%g){
return {-1, -1};
}
m[i] = internal_arrange_mod(m[i], m[j], g);
m[j] /= gcd(m[i], g);
}
}
T prod = 1;
for (int i = 0; i < N; i++){
r[i] %= m[i];
prod *= m[i];
}
return {crt_relatively_prime<T>(r, m), prod};
}
// Garnerのアルゴリズムで元の数を復元する。存在しなければ-1が返り、存在するならばありうるもののうち、最小の非負整数%MODが返る。
//modの最小公倍数も求まる。
template<typename T> constexpr array<T, 2> crt(vector<T> r, vector<T> m, T MOD){
int N = len(r);
assert(N == len(m));
for (int i = 0; i < N-1; i++){
for (int j = i+1; j < N; j++){
T g = gcd(m[i], m[j]);
if ((r[i]-r[j])%g){
return {-1, -1};
}
m[i] = internal_arrange_mod(m[i], m[j], g);
m[j] /= gcd(m[i], g);
}
}
T prod = 1;
for (int i = 0; i < N; i++){
r[i] %= m[i];
prod = prod*m[i]%MOD;
}
return {crt_relatively_prime<T>(r, m, MOD), prod};
}
#endif /* CRT_HPP_ */
void solve(){
ll N;
cin >> N;
vector<ll> A(N);
vector<ll> B(N);
bool all_zero = true;
for (ll i = 0; i < N; i++){
cin >> A[i] >> B[i];
if (A[i] > 0){
all_zero = false;
}
}
auto ans = crt(A,B, 1000000007LL);
print(all_zero ? ans[1] : ans[0]);
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll T = 1;
// cin >> T;
while (T--){
solve();
}
}