#1141339 (C++23) No.186 中華風 (Easy)

• 問題: No.186 中華風 (Easy)
• ユーザー: zoidzium (zz)
• 提出日時: 2025-12-21 16:26:36
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 6,684 bytes
• コンパイル時間: 3,727 ms
• コンパイル使用メモリ: 286,336 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2025-12-21 16:26:41
• 合計ジャッジ時間: 4,756 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
other	AC * 23

ソースコード

#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

xy gcdex(ll a, 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(xy ab) { return gcdex(ab.first, ab.second); }
ll gcd(ll a, ll b) {
  xy ans = gcdex(a, b);
  return abs(a * ans.first + b * ans.second);
}
ll gcd(xy ab) { return gcd(ab.first, ab.second); }
vl gcd(const vl& vec) {
  ll n = vec.size();
  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);
}

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;

/////////////////////////////////////////////////

/////////////////////////////////////////////////

int main() {
  // dbg::unprint = true;

  vl X(3), Y(3);

  rep(i, 3) cin >> X[i] >> Y[i];

  vxy VEC;
  rep(i, 3) VEC.emplace_back(X[i], Y[i]);
  xy ans = ganner(VEC);
  if (ans.first == 0) ans.first = ans.second;
  cout << ans.first << endl;
  return 0;
}