結果
| 問題 | No.187 中華風 (Hard) |
| ユーザー |
 tonegawa
|
| 提出日時 | 2023-06-07 15:09:23 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 29,612 bytes |
| コンパイル時間 | 2,987 ms |
| コンパイル使用メモリ | 197,200 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-09 11:14:44 |
| 合計ジャッジ時間 | 4,046 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | AC | 19 ms
5,376 KB |
| testcase_05 | AC | 18 ms
5,376 KB |
| testcase_06 | AC | 18 ms
5,376 KB |
| testcase_07 | AC | 18 ms
5,376 KB |
| testcase_08 | AC | 17 ms
5,376 KB |
| testcase_09 | AC | 16 ms
5,376 KB |
| testcase_10 | AC | 17 ms
5,376 KB |
| testcase_11 | AC | 18 ms
5,376 KB |
| testcase_12 | AC | 18 ms
5,376 KB |
| testcase_13 | AC | 17 ms
5,376 KB |
| testcase_14 | AC | 17 ms
5,376 KB |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | AC | 2 ms
5,376 KB |
| testcase_18 | AC | 2 ms
5,376 KB |
| testcase_19 | AC | 2 ms
5,376 KB |
| testcase_20 | AC | 14 ms
5,376 KB |
| testcase_21 | AC | 2 ms
5,376 KB |
| testcase_22 | AC | 18 ms
5,376 KB |
| testcase_23 | AC | 1 ms
5,376 KB |
| testcase_24 | AC | 1 ms
5,376 KB |
ソースコード
#line 2 ".lib/template.hpp"
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
template<typename T>
using vec = std::vector<T>;
using namespace std;
template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
dest << p.first << ' ' << p.second;
return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
int sz = v.size();
if(sz==0) return dest;
for(int i=0;i<sz;i++){
int m = v[i].size();
for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
}
return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
int sz = v.size();
if(sz==0) return dest;
for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
dest << v[sz-1];
return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
if(sz==0) return dest;
for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
dest << v[sz-1];
return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
for(auto itr=v.begin();itr!=v.end();){
dest << *itr;
itr++;
if(itr!=v.end()) dest << ' ';
}
return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
for(auto itr=v.begin();itr!=v.end();){
dest << '(' << itr->first << ", " << itr->second << ')';
itr++;
if(itr!=v.end()) dest << '\n';
}
return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
std::vector<T> v(sz);
for(int i=0;i<sz;i++) std::cin >> v[i];
return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
for(int i=0;i<sz;i++) v[i] = read_vec<T>(tail...);
return v;
}
void io_init(){
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
}
#line 3 ".lib/math/integer.hpp"
#include <cstdint>
#line 8 ".lib/math/integer.hpp"
#include <limits>
#line 13 ".lib/math/integer.hpp"
// a^k >= xとなる最小のa^k
uint64_t ceil_pow(uint64_t x, uint64_t a){
assert(a > 1);
if(x == 0) return 1;
static uint64_t INF = std::numeric_limits<uint64_t>::max();
if(a == 2){
uint64_t ret = uint64_t(1) << (63 - __builtin_clzll(x));
if(ret == x) return x;
assert(ret <= (INF >> 1));
return ret << 1;
}
if(a > 10){
uint64_t ret = 1;
while(true){
if(ret > x / a) break;
ret *= a;
}
if(ret == x) return ret;
assert(ret <= INF / a);
return ret * a;
}
static std::vector<std::vector<uint64_t>> pow_table(11);
if(pow_table[a].empty()){
uint64_t tmp = 1;
pow_table[a].push_back(1);
while(true){
if(tmp > INF / a) break;
pow_table[a].push_back(tmp *= a);
}
}
auto itr = std::lower_bound(pow_table[a].begin(), pow_table[a].end(), x);
assert(itr != pow_table[a].end());
return *itr;
}
// 2^k >= xとなる最小の2^k
uint64_t ceil_2_pow(uint64_t x){
static uint64_t INF = std::numeric_limits<uint64_t>::max();
uint64_t ret = uint64_t(1) << (63 - __builtin_clzll(x));
if(ret == x) return x;
assert(ret <= (INF >> 1));
return ret << 1;
}
// a^k <= xを満たす最大のa^k
uint64_t floor_pow(uint64_t x, uint64_t a){
assert(x > 0 && a > 1);
if(a == 2) return uint64_t(1) << (63 - __builtin_clzll(x));
if(a > 10){
uint64_t ret = 1;
while(true){
if(ret > x / a) return ret;
ret *= a;
}
}
static std::vector<std::vector<uint64_t>> pow_table(11);
static uint64_t INF = std::numeric_limits<uint64_t>::max();
if(pow_table[a].empty()){
uint64_t tmp = 1;
pow_table[a].push_back(1);
while(true){
if(tmp > INF / a) break;
pow_table[a].push_back(tmp *= a);
}
}
return *--std::upper_bound(pow_table[a].begin(), pow_table[a].end(), x);
}
// 10 = 10 * 1 + 0
// 10 = 9 * 1 + 1
// 10 = 8 * 1 + 2
// 10 = 7 * 1 + 3
// 10 = 6 * 1 + 4
// 10 = 5 * 2 = 0
// 10 = 4 * 2 + 2
// 10 = 3 * 3 = 1
// 10 = 2 * 5 + 0
// 10 = 1 * 10 + 10
// 商としてありえる数は高々 2 * √x 通り
// また, [dmin, dmax]が存在して, この区間の数で割った商は全て等しく, 区間に含まれない任意の数で割った商とは異なる
// 可能な組{商, dmin, dmax}を列挙
// 商が[√x, x]の時はdmin = dmax
std::vector<std::array<long long, 3>> divrange(long long x){
if(x == 1) return {{1, 1, 1}};
std::vector<std::array<long long, 3>> l{{x, 1, 1}}, r{{1, x, x}};
int ls = 0, rs = 0;
long long i = 2;
for(; i * i <= x; i++){
long long d = x / i;
if(l[ls][0] != d) l.push_back({d, i, i}), ls++;
else l[ls][1] = i;
if(i * i == x) continue;
if(r[rs][0] != i) r[rs][1] = d + 1, r.push_back({i, d, d}), rs++;
else r[rs][2] = x;
}
if(l[ls][0] == r[rs][0]) l[ls][2] = r[rs][2], r.pop_back();
std::reverse(r.begin(), r.end());
r[0][1] = i;
l.insert(l.end(), r.begin(), r.end());
return l;
}
// a ^ k <= xを満たす最大のa
uint64_t kth_root_stable(uint64_t x, uint64_t k){
if(!x) return 0;
if(k == 1 || x == 1) return x;
if(k >= 64) return 1;
uint64_t l = 1, r = x;
const static uint64_t threshold = std::numeric_limits<uint64_t>::max();
while(r - l > 1){
bool f = false;
uint64_t mid = l + ((r - l) >> 1), z = 1;
uint64_t lim = threshold / mid;
for(int i = 0; i < k; i++){
if(z > lim){
f = true;
break;
}
z *= mid;
}
if(f | (z > x)) r = mid;
else l = mid;
}
return l;
}
// a^k <= x を満たす最大のa
uint64_t kth_root_fast(uint64_t x, uint64_t k){
if(x <= 1) return (!k ? 1 : x);
if(k <= 2) return (k <=1 ? !k ? 1 : x : sqrtl(x));
if(k >= 64||!(x >> k)) return 1;
const static int sz[8] = {40, 31, 27, 24, 22, 21, 20, 19};
static std::vector<std::vector<uint64_t>> table;
if(table.empty()){
table.resize(40);
for(int i = 0; i < 40; i++){
for(uint64_t j = 0; j < 8 && sz[j] > i; j++){
table[i].push_back((!i ? 1 : table[i - 1][j]) *(j + 3));
}
}
}
if(k >= 19){
int ans = 10;
for(;ans > 2; ans--){
if(sz[ans - 3]<k || table[k - 1][ans - 3] > x) continue;
return ans;
}
return 2;
}
uint64_t r = (k != 3 ? pow(x, (1.0 + 1e-6) / k) : cbrt(x) + 1);
const static uint64_t threshold = std::numeric_limits<uint64_t>::max();
while(true){
uint64_t lim = threshold / r, z = 1;
for(int i = 0; i < k; i++, z *= r) if(z > lim) goto upper;
if(z > x) upper: r--;
else break;
}
return r;
}
namespace prime_sieve{
std::vector<int> primes, min_factor;// 素数, 各数を割り切る最小の素数
// O(MAX_N loglog MAX_N)
void init(int MAX_N){
min_factor.resize(MAX_N + 1, -1);
for(int i = 2; i <= MAX_N; i++){
if(min_factor[i] == -1){
primes.push_back(i);
min_factor[i] = i;
}
for(int p : primes){
if((long long)p * i > MAX_N || p > min_factor[i]) break;
min_factor[p * i] = p;
}
}
}
bool is_prime(int n){
assert(n < min_factor.size());
return n == min_factor[n];
}
// {{素因数, 数}}, O(log n)
std::vector<std::pair<int, int>> factorize(int n){
assert(n < min_factor.size());
std::vector<std::pair<int, int>> ret;
while(n > 1){
int cnt = 0, f = min_factor[n];
while(n % f == 0){
n /= f;
cnt++;
}
ret.push_back({f, cnt});
}
return ret;
}
// 約数列挙, O(√n)
std::vector<int> divisor(int n){
auto p = factorize(n);
std::vector<std::vector<int>> x;
for(int i = 0; i < p.size(); i++){
x.push_back(std::vector<int>{1});
for(int j = 0; j < p[i].second; j++) x[i].push_back(x[i][j] * p[i].first);
}
int l = 0, r = 1;
std::vector<int> ret{1};
for(int i = 0; i < x.size(); i++){
for(auto e : x[i]){
for(int j = l; j < r; j++){
ret.push_back(ret[j] * e);
}
}
l = r;
r = ret.size();
}
return std::vector<int>(ret.begin() + l, ret.end());
}
};
std::vector<long long> v{1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,36756720,43243200,61261200,73513440,110270160,122522400,147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,1102701600,1396755360,2095133040,2205403200,2327925600,2793510720,3491888400,4655851200,5587021440,6983776800,10475665200,13967553600,20951330400,27935107200,41902660800,48886437600,64250746560,73329656400,80313433200,97772875200,128501493120,146659312800,160626866400,240940299600,293318625600,321253732800,481880599200,642507465600,963761198400,1124388064800,1606268664000,1686582097200,1927522396800,2248776129600,3212537328000,3373164194400,4497552259200,6746328388800,8995104518400,9316358251200,13492656777600,18632716502400,26985313555200,27949074753600,32607253879200,46581791256000,48910880818800,55898149507200,65214507758400,93163582512000,97821761637600,130429015516800,195643523275200,260858031033600,288807105787200,391287046550400,577614211574400,782574093100800,866421317361600,1010824870255200,1444035528936000,1516237305382800,1732842634723200,2021649740510400,2888071057872000,3032474610765600,4043299481020800,6064949221531200,8086598962041600,10108248702552000,1212898443062400,18194847664593600,20216497405104000,24259796886124800,30324746107656000,36389695329187200,48519593772249600,60649492215312000,72779390658374400,74801040398884800,106858629141264000,112201560598327200,149602080797769600,224403121196654400,299204161595539200,374005201994424000,448806242393308800,673209363589963200,748010403988848000,897612484786617600};
std::vector<long long> ans{1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,160,168,180,192,200,216,224,240,256,288,320,336,360,384,400,432,448,480,504,512,576,600,640,672,720,768,800,864,896,960,1008,1024,1152,1200,1280,1344,1440,1536,1600,1680,1728,1792,1920,2016,2048,2304,2400,2688,2880,3072,3360,3456,3584,3600,3840,4032,4096,4320,4608,4800,5040,5376,5760,6144,6720,6912,7168,7200,7680,8064,8192,8640,9216,10080,10368,10752,11520,12288,12960,13440,13824,14336,14400,15360,16128,16384,17280,18432,20160,20736,21504,23040,24576,25920,26880,27648,28672,28800,30720,32256,32768,34560,36864,40320,41472,43008,46080,48384,49152,51840,53760,55296,57600,61440,62208,64512,65536,69120,73728,80640,82944,86016,92160,96768,98304,103680
};
// 高度合成数(N以下の数の中で最も多い約数を持つ数)
// {N以下の高度合成数, その約数}
std::pair<long long, long long> highly_composite_number(long long N){
assert(0 < N && N <= 1000000000000000000);
int idx = upper_bound(v.begin(), v.end(), N) - v.begin() - 1;
assert(idx != 0);
return {v[idx], ans[idx]};
}
long long llpow(long long a, long long b){
long long ret = 1, mul = a;
while(b){
if(b & 1) ret *= mul;
mul *= mul;
b >>= 1;
}
return ret;
}
long long gcd(long long _a, long long _b) {
uint64_t a = abs(_a), b = abs(_b);
if(a == 0) return b;
if(b == 0) return a;
int shift = __builtin_ctzll(a | b);
a >>= __builtin_ctzll(a);
do{
b >>= __builtin_ctzll(b);
if(a > b) std::swap(a, b);
b -= a;
}while(b);
return (a << shift);
}
// 64bitに収まらない可能性あり
long long lcm(long long a, long long b){
return __int128_t(a * b) / gcd(a, b);
}
std::tuple<long long, long long, long long> extgcd(long long a, long long b){
long long x, y;
for(long long u = y = 1, v = x = 0; a;){
long long q = b / a;
std::swap(x -= q * u, u);
std::swap(y -= q * v, v);
std::swap(b -= q * a, a);
}
return {x, y, b};//return {x, y, gcd(a, b)} s.t. ax + by = gcd(a, b)
}
// ak + b のl <= k < rにおける和
template<typename T = long long>
T arithmetic_sum(T a, T b, T l, T r){
return a * (r * (r - 1) - l * (l - 1)) / 2 + b * (r - l);
}
// !
struct barrett_reduction{
unsigned int mod;
unsigned long long m;
barrett_reduction(unsigned int _mod) : mod(_mod){
m = ((__uint128_t)1 << 64) / mod;
}
unsigned int reduce(unsigned int a){
unsigned long long q = ((__uint128_t)a * m) >> 64;
a -= q * mod; // 0 <= a < 2 * mod
// return a;
return a >= mod ? a - mod : a;
}
unsigned int mul(unsigned int a, unsigned int b){
return reduce((unsigned long long)a * b);
}
// {gcd(a, mod), x}, such that a * x ≡ gcd(a, mod)
std::pair<unsigned int, unsigned int> inv(unsigned int a){
if(a >= mod) a = reduce(a);
if(a == 0) return {mod, 0};
unsigned int s = mod, t = a;
long long m0 = 0, m1 = 1;
while(t){
int u = s / t;
s -= t * u;
m0 -= m1 * u;
std::swap(m0, m1);
std::swap(s, t);
}
if(m0 < 0) m0 += mod / s;
return {s, m0};
}
};
// 64bit mod対応
struct montgomery_reduction_64bit{
private:
// [0, 2 * MOD)
inline uint64_t reduce_unsafe(__uint128_t x) const{
x = (x + ((uint64_t)x * (uint64_t)NEG_INV) * MOD) >> 64;
return x;
}
void _set_mod(uint64_t mod){
assert(mod < (1ULL << 63));
MOD = mod;
NEG_INV = 0;
__uint128_t s = 1, t = 0;
for(int i = 0; i < 64; i++){
if (~t & 1) {
t += MOD;
NEG_INV += s;
}
t >>= 1;
s <<= 1;
}
R2 = ((__uint128_t)1 << 64) % MOD;
R2 = R2 * R2 % MOD;
}
__uint128_t MOD, NEG_INV, R2;
public:
montgomery_reduction_64bit(){}
montgomery_reduction_64bit(uint64_t mod){_set_mod(mod);}
void set_mod(uint64_t mod){
_set_mod(mod);
}
uint64_t mod()const{
return MOD;
}
inline uint64_t generate(uint64_t x)const{
return reduce((__uint128_t)x * R2);
}
inline uint64_t reduce(__uint128_t x)const{
x = (x + ((uint64_t)x * (uint64_t)NEG_INV) * MOD) >> 64;
return x < MOD ? x : x - MOD;
}
// [0, 2MOD)
inline uint64_t mul(uint64_t mx, uint64_t my)const{
return reduce_unsafe((__uint128_t)mx * my);
}
inline uint64_t mul_safe(uint64_t mx, uint64_t my)const{
return reduce((__uint128_t)mx * my);
}
// [0, 2MOD)
inline uint64_t add(uint64_t mx, uint64_t my)const{
return (mx >= MOD ? mx - MOD : mx) + (my >= MOD ? my - MOD : my);
}
inline uint64_t add_safe(uint64_t mx, uint64_t my)const{
uint64_t res = (mx >= MOD ? mx - MOD : mx) + (my >= MOD ? my - MOD : my);
return res >= MOD ? res - MOD : res;
}
// [0, 2MOD)
inline uint64_t sub(uint64_t mx, uint64_t my)const{
if(my >= MOD) my -= MOD;
return mx >= my ? mx - my : mx + MOD - my;
}
inline uint64_t sub_safe(uint64_t mx, uint64_t my)const{
if(my >= MOD) my -= MOD;
uint64_t res = mx >= my ? mx - my : mx + MOD - my;
return res >= MOD ? res - MOD : res;
}
};
// maと戻り値はモンゴメリ表現
unsigned long long _mod_pow_mr(unsigned long long ma, unsigned long long b, const montgomery_reduction_64bit &mr){
unsigned long long res = mr.generate(1), mul = ma;
while(b){
if(b & 1) res = mr.mul(res, mul);
mul = mr.mul(mul, mul);
b >>= 1;
}
if(res >= mr.mod()) return res - mr.mod();
return res;
}
unsigned long long mod_pow_mr(unsigned long long a, unsigned long long b, unsigned long long m){
montgomery_reduction_64bit mr(m);
return mr.reduce(_mod_pow_mr(mr.generate(a), b, mr));
}
static std::vector<unsigned long long> generate_random_a(int k){
static std::random_device seed_gen;
static std::mt19937_64 engine(seed_gen());
std::vector<unsigned long long> res(k);
for(int i = 0; i < k; i++) res[i] = engine();
return res;
}
bool _miller_rabin_mr(unsigned long long n, const montgomery_reduction_64bit &mr){
static constexpr int k = 10;
static std::vector<int> small_p{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
static std::vector<unsigned long long> A = generate_random_a(k);
static std::vector<unsigned long long> B{2, 3, 5, 7};// https://t5k.org/prove/prove2_3.html
if(n <= 1) return false;
if(n <= 50){
for(int l = n < 20 ? 0 : 8, r = n < 20 ? 8 : 15; l < r; l++) if(small_p[l] == n) return true;
return false;
}
if(!(n & 1)) return false;
unsigned long long d = n - 1;
unsigned long long one = mr.generate(1), mone = mr.generate(n - 1);
d >>= __builtin_ctzll(d);
for(unsigned long long a : (n < 118670087467 ? B : A)){
if(a % n == 0) continue;
unsigned long long d2s = d; // d * 2^s, 0 <= s <= (n - 1)が2で割れる回数
unsigned long long y = _mod_pow_mr(mr.generate(a), d, mr);
while(d2s != n - 1 && y != one && y != mone){
y = mr.mul_safe(y, y);
d2s <<= 1;
}
if(y != mone && !(d2s & 1)) return false;
}
return true;
}
bool miller_rabin_mr(unsigned long long n){
montgomery_reduction_64bit mr(n);
return _miller_rabin_mr(n, mr);
}
// https://en.wikipedia.org/wiki/Binary_GCD_algorithm
unsigned long long binary_gcd(unsigned long long a, unsigned long long b){
if(!a || !b) return !a ? b : a;
int shift = __builtin_ctzll(a | b); // [1] gcd(2a', 2b') = 2 * gcd(a', b')
a >>= __builtin_ctzll(a);
do{
// if b is odd
// gcd(2a', b) = gcd(a', b), if a = 2a'(a is even)
// gcd(a, b) = gcd(|a - b|, min(a, b)), if a is odd
b >>= __builtin_ctzll(b); // make b odd
if(a > b) std::swap(a, b);
b -= a;
}while(b); // gcd(a, 0) = a
return a << shift; // [1]
}
unsigned long long generate_random_prime(unsigned long long min_n = 2, unsigned long long max_n = ~0){
static std::random_device seed_gen;
static std::mt19937_64 engine(seed_gen());
unsigned long long len = max_n - min_n + 1;
// about 40 tries per iteration. https://en.wikipedia.org/wiki/Prime_number_theorem
// It brokes when π(max_n) == π(min_n - 1)
while(true){
unsigned long long a = engine() % len + min_n;
if(miller_rabin_mr(a)){
return a;
}
}
}
namespace rho_factorization{
unsigned long long rho(unsigned long long n){
static std::vector<int> small_p{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
for(int sp : small_p) if(n % sp == 0) return sp; // n < 50
montgomery_reduction_64bit mr(n);
if(_miller_rabin_mr(n, mr)) return n;
auto try_factorize = [n, mr](unsigned long long c){
c = mr.generate(c);
auto f = [mr, c](unsigned long long mx){
return mr.add(mr.mul(mx, mx), c);
};
unsigned long long m = 1LL << ((64 - __builtin_clzll(n)) / 8);
unsigned long long y = n, r = 1, q = 1;
unsigned long long x, g, k, ys;
do{
x = y;
y = mr.generate(y);
for(int i = 0; i < r; i++) y = f(y);
y = mr.reduce(y);
k = 0;
while(k < r && g == 1){
q = mr.generate(q);
y = mr.generate(y);
ys = y;
for(int i = 0; i < std::min(m, r - k); i++){
y = f(y);
unsigned long long z = mr.reduce(y);
q = mr.mul(q, mr.generate(x > z ? x - z : z - x));
}
y = mr.reduce(y);
g = binary_gcd(mr.reduce(q), n);
k += m;
}
r <<= 1;
}while(g == 1);
if(g == n){
do{
ys = f(ys);
unsigned long long z = mr.reduce(ys);
g = binary_gcd(x > z ? x - z : z - x, n);
}while(g == 1);
}
return g; // g == n when failure
};
unsigned long long c = 1, res = n;
do{
res = try_factorize(c);
// c = generate_random_prime(2, n - 1);
c = (c + 1) % n;
}while(res == n);
return res;
}
std::vector<unsigned long long> factorize(unsigned long long n){
if(n <= 1) return {};
unsigned long long x = rho(n);
if(x == n) return {x};
auto l = factorize(x);
auto r = factorize(n / x);
l.insert(l.end(), r.begin(), r.end());
return l;
}
// 素因数の集合(重複なし, ソート済)を返す
std::vector<unsigned long long> prime_factor(unsigned long long n){
auto p = factorize(n);
sort(p.begin(), p.end());
p.erase(std::unique(p.begin(), p.end()), p.end());
return p;
}
// 10^18以下の高度合成数 897612484786617600の約数が103680個なので全列挙して良さそう
std::vector<unsigned long long> divisor(unsigned long long n){
auto p = factorize(n);
sort(p.begin(), p.end());
std::vector<std::pair<unsigned long long, int>> x;
for(int i = 0; i < p.size(); i++){
if(!i || p[i] != p[i - 1]) x.push_back({p[i], 1});
else x.back().second++;
}
int sz = 1;
for(auto [p_cur, cnt] : x) sz *= cnt + 1;
std::vector<unsigned long long> res(sz);
res[0] = 1;
int r_prev = 1, r = 1;
for(auto [p_cur, cnt] : x){
unsigned long long ppow = 1;
for(int c = 0; c < cnt; c++){
ppow *= p_cur;
for(int i = 0; i < r_prev; i++){
res[r++] = res[i] * ppow;
}
}
r_prev = r;
}
return res;
}
}
//---tips---
//φ(n) := [1, n]の中でnと互いに素な正整数の数
//φ(n) = n * π{p:prime factor of n}(1 - 1/p)
//aとnが互いに素な場合, a^φ(n) ≡ 1 (mod n)
unsigned long long totient(unsigned long long n){
unsigned long long res = n;
auto prims = rho_factorization::prime_factor(n);
for(auto p : prims) res -= res / p;
return res;
}
// n以下のtotient_sum
std::vector<unsigned long long> totient_sum_table(unsigned long long n){
std::vector<unsigned long long> res(n + 1);
std::iota(res.begin() + 1, res.end(), 0);
res[1] = 1;
for(int i = 2; i <= n; i++){
// prime
if(res[i] == i - 1){
for(int j = 2 * i; j <= n; j += i){
res[j] -= res[j] / i;
}
}
}
for(int i = 2; i <= n; i++) res[i] += res[i - 1];
return res;
}
// [1]
// totient_sum(n) = (i, j){1 <= i <= n, 1 <= j <= i}となるペアの数 - そのうちgcd(i, j) != 1であるものの数
// = n * (n + 1) / 2 - ∑{2 <= g <= n} gcd(i, j) == gのペア
// = n * (n + 1) / 2 - ∑{2 <= g <= n} totient_sum(n / g)
// この演算をメモ化再帰で行った時の n / g (切り捨て)の種類数について考える
// [2]
// floor(x / ab) = floor(floor(x / a) / b)
// 証明:
// x = qab + r (0 <= r < ab)とすると
// 左辺 = floor(q + r / ab) = q
// 右辺 = floor((qb + r') / b) (0 <= r' < b) = q
// [3]
// [2]よりnを正整数で0回以上除算した時に得られる商はO(√n)種類
__uint128_t totient_sum(unsigned long long n){
static std::vector<unsigned long long> low;
if(low.empty()) low = totient_sum_table(std::min(n, (unsigned long long)4000000));
std::unordered_map<unsigned long long, __uint128_t> mp;
unsigned long long memo_max = 0;
auto tsum = [&](auto &&tsum, unsigned long long m)->__uint128_t{
if(m < low.size()) return low[m];
if(m <= memo_max) return mp.at(m);
__uint128_t res = (__uint128_t)m * (m + 1) / 2;
auto d = divrange(m);
std::reverse(d.begin(), d.end());
for(auto [q, a, b] : d){
if(q == m) continue;
res -= (b - a + 1) * tsum(tsum, q);
}
mp.emplace(m, res);
memo_max = m;
return res;
};
return tsum(tsum, n);
}
// p: 素数
unsigned long long is_primitive_root(unsigned long long p){
static std::random_device seed_gen;
static std::mt19937_64 engine(seed_gen());
//assert(miller_rabin_mr(p));
auto primes = rho_factorization::prime_factor(p - 1);
while(true){
bool f = true;
unsigned long long a = engine() % (p - 1) + 1;
for(unsigned long long pk : primes){
// a ^ (p - 1) / pk ≡ 1 (mod p) -> no
if(mod_pow_mr(a, (p - 1) / pk, p) == 1){
f = false;
break;
}
}
if(f) return a;
}
}
// ∑{i, 0 <= i < n} floor((ai + b) / m)
// n, m, a, b <= 10^9
long long floor_sum(long long n, long long m, long long a, long long b){
long long ans = 0;
if(a >= m){
ans += (n - 1) * n * (a / m) / 2;
a %= m;
}
if(b >= m){
ans += n * (b / m);
b %= m;
}
// 変形:
// https://rsk0315.hatenablog.com/entry/2020/12/13/231307
// https://atcoder.jp/contests/practice2/editorial/579
long long y_max = a * n + b;
if(y_max >= m) ans += floor_sum(y_max / m, a, m, y_max % m);
return ans;
}
// min((ax + b) % mod) x in[l, r) , 0 <= l < r
long long min_linear_mod(long long a, long long b, long long l, long long r, long long mod){
assert(l <= 0 && l < r);
a %= mod;
b = (b + a * l) % mod; // [0, r - l)に変換
r -= l;
if(a == 0) return b;
long long upper = floor_sum(r, mod, a, b);
long long L = 0, R = b + 1;
// 定数倍高速化
long long tmp_val = b, tmp_idx = 0;
for(int i = 0; i < 10; i++){
long long sa = mod - tmp_val;
tmp_idx += (sa + a - 1) / a;
tmp_val = (tmp_idx * a + b) % mod;
if(tmp_idx >= r) break;
R = std::min(R, tmp_val + 1);
}
while(R - L > 1){
long long mid = (L + R) / 2;
if(upper == floor_sum(r, mod, a, b - mid)) L = mid;
else R = mid;
}
return L;
}
///
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
/////
// m_iで割るとr_i余る情報から(全ての条件を満たすlcm(m_i)以下の数)%modを返す
// mが互いに素でないと壊れる
// O(n^2)
#line 754 ".lib/math/integer.hpp"
long long garner_coprime(std::vector<long long> r, std::vector<long long> m, long long mod){
int n = r.size();
assert(n == m.size());
// ans = r_1 + x_1 * m_1 + x_2 * m_1 * m_2 ...
// x_i = (r_i - (i - 1項までの和)) / (m_1 * m_2 ... m_i-1) mod m_i
// M_i := (m_1 * m_2 ... m_i - 1) mod m_i
std::vector<long long> accum(n + 1, 0), M(n + 1, 1);
m.push_back(mod);
for(int i = 0; i < n; i++){
auto [g, inv] = inv_gcd(M[i], m[i]);
assert(g == 1);
long long x = (((__int128_t)r[i] - accum[i]) * inv) % m[i];
if(x < 0) x += m[i];
for(int j = i + 1; j <= n; j++){
accum[j] = (accum[j] + (__int128_t)M[j] * x) % m[j];
M[j] = ((__int128_t)M[j] * m[i]) % m[j];
}
}
return accum[n];
}
// m_iで割るとr_i余る情報から(全ての条件を満たすlcm(m_i)以下の数)%modを返す
// 解が無い場合は-1
long long garner(std::vector<long long> &r, std::vector<long long> &m, long long mod){
int n = r.size();
assert(n == m.size());
static std::unordered_map<long long, std::pair<long long, int>> P;
for(int i = 0; i < n; i++){
auto f = rho_factorization::factorize(m[i]);
std::sort(f.begin(), f.end());
f.push_back(0);
long long p = -1, p_pow = 1;
for(int j = 0; j < f.size(); j++){
if(f[j] == p){
p_pow *= p;
}else{
if(p != -1){
auto itr = P.find(p);
if(itr == P.end()){
P.emplace(p, std::make_pair(p_pow, i));
}else{
auto [p_pow_max, idx_max] = itr->second;
if(r[idx_max] % p_pow != r[i] % p_pow) return -1; // 解なし, 例: 2で割って1余りつつ0余る数
if(p_pow_max < p_pow){
m[idx_max] /= p_pow_max;
r[idx_max] %= m[idx_max];
itr->second = std::make_pair(p_pow, i);
}else{
m[i] /= p_pow;
r[i] %= m[i];
}
}
}
p = f[j];
p_pow = p;
}
}
}
return garner_coprime(r, m, mod);
}
#line 3 "a.cpp"
int main(){
io_init();
int n;
std::cin >> n;
vec<ll> r(n), m(n);
range(i, 0, n) std::cin >> r[i] >> m[i];
std::cout << garner(r, m, 1000000007) << '\n';
}