#1142189 (C++23) No.187 中華風 (Hard)

• 問題: No.187 中華風 (Hard)
• ユーザー: zoidzium (zz)
• 提出日時: 2025-12-29 16:32:28
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 17,743 bytes
• コンパイル時間: 3,176 ms
• コンパイル使用メモリ: 295,160 KB
• 実行使用メモリ: 7,852 KB
• 最終ジャッジ日時: 2025-12-29 16:32:35
• 合計ジャッジ時間: 7,648 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
other	AC * 5 WA * 20

ソースコード

#include <bits/stdc++.h>

#include <cassert>
using namespace std;

using ull = unsigned long long;
using ll = long long;
using xy = pair<ll, ll>;
using coord = pair<double, double>;
using bs8 = bitset<8>;
using bs16 = bitset<16>;
using bs32 = bitset<32>;
using bs64 = bitset<64>;

using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vvs = vector<vs>;
using vxy = vector<xy>;
using vvxy = vector<vxy>;
using vcoord = vector<coord>;
using vvcoord = vector<vcoord>;

#define rep(var, n) for (ll var = 0; var < (ll)(n); var++)
#define cnt(var, n, m) for (ll var = (n); var <= (ll)(m); var++)
#define rcnt(var, n, m) for (ll var = (n); var >= (ll)(m); var--)
#define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;
#define ZINIT 1

#if __has_include("zout.h")
#include "zout.h"
#else
namespace zz_print {
class dbg {
 public:
  static bool unprint;
  static string margin;
  static string separated;
  static string indentS;
  static int hierarchical;
  static int topHier;
  static int precision;
  static bool exponential;

  static void setFloat(const int& prec, const bool& expo) {
    precision = prec;
    exponential = expo;
  };

  template <int hier = 0, int sep = 2, int mgn = 1, typename... Args>
  static void zout(Args&&... args) {};
};
bool dbg::unprint = false;
string dbg::margin = "";
string dbg::separated = "";
string dbg::indentS = "";
int dbg::hierarchical = 0;
int dbg::topHier = 0;
int dbg::precision = 6;
bool dbg::exponential = false;
};  // namespace zz_print
using namespace zz_print;
#endif

namespace zz_random {
struct Xoshiro256 {
  ull s[4];
  static inline ull rotl(ull x, int k) { return (x << k) | (x >> (64 - k)); }
  static inline ull splitmix64(ull& x) {
    ull z = (x += 0x9e3779b97f4a7c15ULL);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
    z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
    return z ^ (z >> 31);
  }
  explicit Xoshiro256(ull seed = 1) {
    ull x = seed;
    rep(i, 4) s[i] = splitmix64(x);
  }
  inline ull next() {
    ull res = rotl(s[1] * 5, 7) * 9;
    ull t = s[1] << 17;
    s[2] ^= s[0];
    s[3] ^= s[1];
    s[1] ^= s[2];
    s[0] ^= s[3];
    s[2] ^= t;
    s[3] = rotl(s[3], 45);
    return res;
  }
  inline ull operator()() { return next(); }

  /// integer [0, n)
  inline ll intn(const ll& n = 2) { return (ll)(next() % (ull)n); }
  /// integer [l, r]
  inline ll range(const ll& l, const ll& r) { return l + intn(r - l + 1); }
  /// real [0, 1)
  inline double real() { return (next() >> 11) * (1.0 / (1ULL << 53)); }
  inline double real(const double& r) { return real() * r; }
  inline double real(const double& l, const double& r) { return (l + real() * (r - l)); }

  // Box–Muller 用キャッシュ
  bool has_spare = false;
  double spare;

  /// 標準正規分布 N(0,1)
  inline double normal01() {
    if (has_spare) {
      has_spare = false;
      return spare;
    }

    double u = 0.0, v;
    while (u <= 0.0) u = real();  // (0,1)
    v = real();

    double r = sqrt(-2.0 * log(u));
    double theta = 2.0 * M_PI * v;

    spare = r * sin(theta);
    has_spare = true;
    return r * cos(theta);
  }

  /// 正規分布 N(mean, stddev^2)
  inline double normal(const double& mean, const double& stddev) { return mean + stddev * normal01(); }
};

};  // namespace zz_random
using namespace zz_random;

xy gcdex(const ll a, const ll b) {
  xy ans;

  if (abs(a) < abs(b)) {
    ans = gcdex(b, a);
    swap(ans.first, ans.second);
    return ans;
  } else if (b == 0) {
    return xy{1, 0};
  }

  //  a > b
  //  da x + db y = d
  //   a x +  b y = 1
  //   (b(a/b) + a%b) x + b y = 1
  //   b ((a/b)x + y) + a%b x = 1
  //   b x' + a%b y' = 1
  //
  //   |x|   | 0   1  | |x'|
  //   | | = |        |*|  |
  //   |y|   | 1 -a/b | |y'|
  //
  ans = gcdex(b, a % b);
  return xy{ans.second, ans.first - (a / b) * ans.second};
};
xy gcdex(const xy ab) { return gcdex(ab.first, ab.second); }
ll gcd(const ll a, const ll b) {
  xy ans = gcdex(a, b);
  return abs(a * ans.first + b * ans.second);
}
ll gcd(const xy ab) { return gcd(ab.first, ab.second); }
ll gcd(const vl& vec) {
  ll n = vec.size();
  if (n == 0) return 1;
  if (n == 1) return vec[0];
  vl subvec;
  rep(i, n / 2) subvec.push_back(gcd(vec[2 * i], vec[2 * i + 1]));
  if (n % 2) subvec.push_back(vec[n - 1]);
  return gcd(subvec);
}
ll lcm(const ll a, const ll b) { return (a * (b / gcd(a, b))); }
ll lcm(const xy ab) { return lcm(ab.first, ab.second); }
ll lcm(const vl& vec) {
  ll n = vec.size();
  if (n == 0) return 1;
  if (n == 1) return vec[0];
  vl subvec;
  rep(i, n / 2) subvec.push_back(lcm(vec[2 * i], vec[2 * i + 1]));
  if (n % 2) subvec.push_back(vec[n - 1]);
  return lcm(subvec);
}

xy ganner(const vxy& vec) {
  ll n = vec.size();
  if (n == 0) return xy{-1, 0};
  if (n == 1) return vec[0];

  vxy subvec;
  rep(i, n / 2) {
    ll r1 = vec[2 * i].first, r2 = vec[2 * i + 1].first;
    ll p1 = vec[2 * i].second, p2 = vec[2 * i + 1].second;

    // p1 * x + p2 * y = d  [%lcm(p1,p2)]
    // d*p1' * x + d*p2' * y = d [%(p1*p2/d)]
    // (d*p1' * x + d*p2' * y) * ((r2 - r1)/d) = d * ((r2 - r1)/d) [%(p1*p2/d)]
    // s * p1 * x + s * p2 * y = r2 - r1 [%(p1*p2/d)]
    // r1 + (s * x) * p1  = r2 - (s * p2) * y [%(p1*p2/d)]
    //
    // d*s = r2 - r1 [%p2]
    // s = (r2 - r1)/d [%(p2/d)]
    // x = d * 1 / p1 [%p2]
    // x = 1 / p1' [%p2]
    // x = inv(p1') [%p2]
    // x = inv(p1) [%(p2/d)]
    xy ans = gcdex(p1, p2);
    ll d = abs(p1 * ans.first + p2 * ans.second);
    ll mod = (p1 / d) * p2;
    if (((r2 - r1) % d) != 0) return xy{-1, 0};
    ll s = (r2 - r1) / d;
    ll k = (s * ans.first) % (p2 / d);
    if (k < 0) k += p2 / d;

    xy pm = xy{k * p1 + r1, mod};
    pm.first %= mod;
    if (pm.first < 0) pm.first += mod;
    subvec.push_back(pm);
  }

  if (n % 2) subvec.push_back(vec[n - 1]);
  return ganner(subvec);
};

namespace zz_mod {
template <ll mod = 998244353>
class pp {
 public:
  ll val;
  void flush() {
    val %= mod;
    if (val < 0) val += mod;
  };
  void weak_flush() {
    if (val < 0) {
      val += mod;
    } else if (val >= mod) {
      val -= mod;
    }
  };
  pp(ll x = 0) {
    val = x % mod;
    weak_flush();
  };
  friend std::ostream& operator<<(std::ostream& os, const pp<mod>& x) {
    return os << '{' << x.val << '|' << mod << '}';
  };

  pp<mod>& operator+=(const pp<mod>& p) {
    val += p.val;
    weak_flush();
    return *this;
  };
  pp<mod>& operator+=(ll x) {
    val += x % mod;
    weak_flush();
    return *this;
  };
  friend pp<mod> operator+(pp<mod> a, const pp<mod>& b) { return a += b; };
  friend pp<mod> operator+(pp<mod> a, ll x) { return a += x; };
  friend pp<mod> operator+(ll x, pp<mod> a) { return a += x; };

  pp<mod>& operator-=(const pp<mod>& p) {
    val -= p.val;
    weak_flush();
    return *this;
  };
  pp<mod>& operator-=(ll x) {
    val -= x % mod;
    weak_flush();
    return *this;
  };
  friend pp<mod> operator-(pp<mod> a, const pp<mod>& b) { return a -= b; };
  friend pp<mod> operator-(pp<mod> a, ll x) { return a -= x; };
  friend pp<mod> operator-(ll x, const pp<mod>& a) { return pp<mod>(x) -= a; };

  pp<mod>& operator*=(const pp<mod>& p) {
    val = (__int128)val * p.val;
    flush();
    return *this;
  };
  pp<mod>& operator*=(ll x) {
    val = (__int128)val * x;
    flush();
    return *this;
  };
  friend pp<mod> operator*(pp<mod> a, const pp<mod>& b) { return a *= b; };
  friend pp<mod> operator*(pp<mod> a, ll x) { return a *= x; };
  friend pp<mod> operator*(ll x, const pp<mod>& a) { return pp<mod>(x) *= a; };

  pp<mod> inv() {
    xy ans = gcdex(mod, val);
    assert((mod * ans.first + val * ans.second) == 1);
    pp<mod> p(ans.second);
    return p;
  };
  pp<mod>& operator/=(const pp<mod>& p) { return *this *= p.inv(); }
  pp<mod>& operator/=(ll x) { return *this *= gcdex(mod, x).second; }

  friend pp<mod> operator/(pp<mod> a, const pp<mod>& b) { return a /= b; };
  friend pp<mod> operator/(pp<mod> a, ll x) { return a /= x; };
  friend pp<mod> operator/(ll x, const pp<mod>& a) {
    a = a.inv();
    return a /= x;
  };

  pp<mod> exp(ll n) {
    if (n < 0) return inv().exp(-n);
    pp<mod> p = *this, ans(1);
    while (n > 1) {
      if (n & 1) ans *= p;
      p *= p;
      n >>= 1;
    }
    if (n > 0) ans *= p;
    return ans;
  };
};

}  // namespace zz_mod
using namespace zz_mod;

namespace zz_prime {
class prime {
 public:
  static vl sieves;
  static constexpr array<ll, 14> pre_trial_division =
      array<ll, 14>{3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};

  static void set(const ll n) {
    sieves = vl(n + 1, 1);
    ll i = 1;
    cnt(i, 2, n) {
      if (sieves[i] != 1) continue;
      ll j = i;
      j += i;
      while (j <= n) {
        if (sieves[j] == 1) sieves[j] = i;
        j += i;
      }
    }
  };

 public:
  prime(const ll n) { set(n); }
  static void resize(const ll n) {
    if (sieves.size() < (n + 1)) set(n);
  }
  static bool millerRabin(const ll n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if ((n % 2) == 0) return false;
    bool ans = false;
    vl a;
    if (n < 4759123141) {
      a = vl{2, 7, 61};
    } else {
      a = vl{2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    }
    each(ite_a, a) {
      if ((*ite_a) >= n) break;
      ll d = n - 1;
      while ((d % 2) == 0) d >>= 1;
      ll x = 1;
      ll b = (*ite_a) % n;
      ll c = d;
      while (c > 0) {
        if (c & 1) x = ((__int128)x * b) % n;
        b = ((__int128)b * b) % n;
        c >>= 1;
      }

      if (x == 1 || x == (n - 1)) continue;
      bool OK = false;
      while (d < (n - 1)) {
        if (x == (n - 1)) {
          OK = true;
          break;
        }
        x = ((__int128)x * x) % n;
        d <<= 1;
      };
      if (OK) continue;
      return false;
    }
    return true;
  }

  static bool isPrime(const ll x) {
    if (sieves.size() <= x) return millerRabin(x);
    if (x < 2) return false;
    return (sieves[x] == 1);
  }

  static vxy pollardsRho(ll x) {
    if (x < 2) return vxy();
    vl prms;
    Xoshiro256 rnd;

    function<ll(ll, const ll, const ll)> F = [&rnd](ll x, const ll c, const ll m) -> ll {
      return (((__int128)x * x + c) % m);
    };
    function<void(ll)> Pollards = [&rnd, &F, &prms, &Pollards](const ll n) {
      if (n < 2) return;
      if (millerRabin(n)) {
        prms.push_back(n);
        return;
      }
      ll r = sqrtl(n);
      if ((r * r) == n) {
        Pollards(r);
        Pollards(r);
        return;
      }

      while (true) {
        ll a = rnd.range(2, n - 1);
        ll b = a;
        ll c = rnd.range(1, n - 1);
        ll d = 1;
        ll loopCnt = 0;
        do {
          loopCnt++;
          ll e = 1;
          ll k = 64;
          while (k > 0) {
            a = F(a, c, n);
            b = F(F(b, c, n), c, n);
            ll tmp = ((__int128)e * abs(a - b)) % n;
            if (tmp == 0) break;
            e = tmp;
            k--;
          }
          d = gcd(e, n);
        } while (d == 1 && loopCnt < 20);
        if (loopCnt >= 20) continue;
        if (d != n) {
          Pollards(d);
          Pollards(n / d);
          return;
        }
      }
    };
    while ((x & 1) == 0) {
      x >>= 1;
      prms.push_back(2);
    }
    each(ite, pre_trial_division) {
      if (x < (*ite)) break;
      while ((x % (*ite)) == 0) {
        x /= (*ite);
        prms.push_back(*ite);
      }
    }
    Pollards(x);
    vxy ans;
    sort(prms.begin(), prms.end());
    each(ite, prms) {
      if (ans.empty() || ans.back().first != (*ite)) {
        ans.emplace_back(*ite, 1);
      } else {
        ans.back().second++;
      }
    }
    return ans;
  }

  static vxy factor(ll x) {
    if (sieves.size() <= x) return pollardsRho(x);
    vl prms;
    if (x < 2) return vxy();
    while (sieves[x] != 1) {
      prms.push_back(sieves[x]);
      x /= sieves[x];
    }
    if (x != 1) prms.push_back(x);
    sort(prms.begin(), prms.end());
    vxy ans;
    each(ite, prms) {
      if (ans.empty() || ans.back().first != (*ite)) {
        ans.emplace_back(*ite, 1);
      } else {
        ans.back().second++;
      }
    };
    return ans;
  };

  static vl divisor(const vxy& fac, const bool srt) {
    vl ans;
    function<void(ll, ll)> func = [&ans, &fac, &func](ll at, ll e) -> void {
      if (at == fac.size()) return;
      ll a = 1;
      cnt(i, 0, fac[at].second) {
        if (a != 1) ans.push_back(e * a);
        func(at + 1, e * a);
        a *= fac[at].first;
      }
    };
    func(0, 1);
    if (srt) sort(ans.begin(), ans.end());
    return ans;
  }
  static vl divisor(const ll n, const bool srt) { return divisor(factor(n), srt); }
};

vl prime::sieves;
}  // namespace zz_prime
using namespace zz_prime;
/////////////////////////////////////////////////
namespace zz_poly {
ll resize_2exp(vl& a) {
  ll nb = 0;
  while ((1 << nb) < a.size()) nb++;
  a.resize(1 << nb, 0);
  return nb;
}

template <ll mod>
ll getFFTroot(ll len, bool rvs = false) {
  pp<mod> w;
  switch (mod) {
    case 880803841:
      // w = pp<mod>(26).exp(105).val;
      w = pp<mod>(26);
      break;
    case 897581057:
      // w = pp<mod>(3).exp(107).val;
      w = pp<mod>(3);
      break;
    case 998244353:
      // w = pp<mod>(3).exp(119).val;
      w = pp<mod>(3);
      break;
    default:
      assert("convolution nomatch mod" == "");
  }
  if (rvs) return w.inv().exp((mod - 1) / len).val;
  return w.exp((mod - 1) / len).val;
}

template <ll mod>
vl tran(const vl& vec, ll zeta) {
  ll n = vec.size();
  if (n == 1) return vec;
  vl subvec1, subvec2;
  rep(i, n / 2) {
    subvec1.push_back(vec[2 * i]);
    subvec2.push_back(vec[2 * i + 1]);
  }
  vl SUBVEC1 = tran<mod>(subvec1, (zeta * zeta) % mod);
  vl SUBVEC2 = tran<mod>(subvec2, (zeta * zeta) % mod);
  ll w = 1;
  vl ans(n);
  rep(i, n) {
    ans[i] = (SUBVEC1[i % (n / 2)] + SUBVEC2[i % (n / 2)] * w) % mod;
    w = (w * zeta) % mod;
  }
  return ans;
}

template <ll mod>
vl fft(vl& a) {
  resize_2exp(a);
  ll w = getFFTroot<mod>(a.size(), false);
  return tran<mod>(a, w);
}

template <ll mod>
vl fft_reverse(vl& A) {
  resize_2exp(A);
  ll n = A.size();
  ll w = getFFTroot<mod>(n, true);
  vl a = tran<mod>(A, w);
  rep(i, n) a[i] = (pp<mod>(a[i]) / n).val;
  return a;
}

template <ll mod>
vl convolution(vl& a, vl& b) {
  ll n = a.size() + b.size() - 1;
  a.resize(n);
  b.resize(n);
  resize_2exp(a);
  resize_2exp(b);
  n = a.size();
  //  dbg::zout(getFFTroot<mod>(a.size(), false), pp<mod>(getFFTroot<mod>(a.size(), false)).exp(a.size()),
  //          pp<mod>(getFFTroot<mod>(a.size(), false)).exp(a.size() / 2));
  // dbg::zout(getFFTroot<mod>(a.size(), true), pp<mod>(getFFTroot<mod>(a.size(), true)).exp(a.size()),
  //        pp<mod>(getFFTroot<mod>(a.size(), true)).exp(a.size() / 2));
  dbg::zout("convolution a =", a);
  dbg::zout("convolution b =", b);
  vl A = fft<mod>(a);
  vl B = fft<mod>(b);
  dbg::zout("convolution  A=", A);
  dbg::zout("convolution  B=", B);
  vl C(n);
  rep(i, n) C[i] = pp<mod>(A[i] * B[i]).val;
  dbg::zout("convolution  C=", C);
  vl c = fft_reverse<mod>(C);
  dbg::zout("convolution c =", c);
  return c;
}
};  // namespace zz_poly
using namespace zz_poly;
/////////////////////////////////////////////////

bool Gn_pre(vxy& vec) {
  dbg::zout("Gn_pre(", vec, ")");
  ll n = vec.size();
  rep(i, n) {
    rep(j, i) {
      ll d = gcd(vec[i].second, vec[j].second);
      dbg::zout("Gn_pre: vec=", vec);
      dbg::zout("Gn_pre: i,j=", xy{i, j}, vec[i], vec[j]);
      dbg::zout("Gn_pre: d=", d);
      if ((vec[i].first - vec[j].first) % d != 0) return false;
      vec[i].second /= d;
      vec[j].second /= d;
      ll di = gcd(vec[i].second, d);
      ll dj = d / di;
      do {
        d = gcd(di, dj);
        di *= d;
        dj /= d;
      } while (d != 1);
      vec[i].second *= di;
      vec[j].second *= dj;
      vec[i].first %= vec[i].second;
      vec[j].first %= vec[j].second;
    }
  }
  return true;
}

ll Gn(vxy vec, ll mod = -1) {
  if (!Gn_pre(vec)) return -1;
  dbg::zout("Gn vec=", vec);
  ll n = vec.size();

  if (n == 0) return -1;
  if (mod == -1) {
    mod = lcm([&vec]() {
      vl v;
      each(ite, vec) v.push_back(ite->second);
      return v;
    }());
    //   mod++;
  }

  dbg::zout("Gn: mod=", mod, " vec=", vec);
  ll r1 = vec[0].first, p1 = vec[0].second;
  cnt(i, 1, n - 1) {
    // r1 = r1 + (r2 - r1) * inv(p1%p2) * p1
    // p1 = lcm(p1,p2)

    ll r2 = vec[i].first, p2 = vec[i].second;
    dbg::zout("Gn: rp1=", xy{r1, p1}, " rp2=", xy{r2, p2});

    ll d = gcd(p1, p2);
    dbg::zout("Gn: d=", d);
    if ((r2 - r1) % d != 0) return -1;

    xy ans = gcdex(p1 / d, p2 / d);
    dbg::zout("Gn: gcd", xy{p1 / d, p2 / d}, " ans=", ans);

    // x * p1 + y * p2 = d
    // x * (p1/d) + y * (p2/d) = 1
    //

    ll r = ((r2 - r1) / d) % (p2 / d);
    if (r < 0) r += p2 / d;

    ans.first %= p2 / d;
    if (ans.first < 0) ans.first += p2 / d;

    ll t = (r * ans.first) % (p2 / d);
    if (t < 0) t += p2 / d;

    r1 = (r1 + (((__int128)p1 * t) % mod)) % mod;
    if (r1 < 0) r1 += mod;

    p1 = lcm(p1, p2) % mod;
    if (p1 < 0) p1 += mod;
    dbg::zout("Gn: rp=", xy{r1, p1}, " ab=", xy{r, ans.first});
    rcnt(j, i, 0) dbg::zout("[", j, "]=", vl{vec[j].second, r1 % vec[j].second, vec[j].first});
  }
  return r1;
}

int main() {
  ll N;
  cin >> N;
  vl X(N), Y(N);
  rep(i, N) cin >> X[i] >> Y[i];

  vxy vec;
  rep(i, N) vec.emplace_back(X[i], Y[i]);
  ll ans = Gn(vec, 998244353);
  cout << (ans != 0 ? ans : lcm(Y)) << endl;
  return 0;
}