結果

問題 No.186 中華風 (Easy)
ユーザー kenseitogarikenseitogari
提出日時 2023-02-04 12:55:29
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 7,273 bytes
コンパイル時間 3,639 ms
コンパイル使用メモリ 174,564 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-03 10:50:49
合計ジャッジ時間 4,538 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC target("sse4")

#include <algorithm>
#include <atcoder/all>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace atcoder;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

#include <string>  // ヘッダファイルインクルード
#include <typeinfo>
using namespace std;  //  名前空間指定
using namespace std;
using mint = modint998244353;
// using Graph = vector<vector<int>>;  // 重みなしのグラフ
// struct Edge {
//   int to;
//   long long w;
//   Edge(int to, long long w) : to(to), w(w) {}
// };
// using Graph_w = vector<vector<Edge>>;  // 重み付きのグラフ

// using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T>

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const int inf = pow(10, 9);
const ll INF = 1e18;
const int MX = 100001;  // check the limits, dummy

const ll infl = 1LL << 60;
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T>
void print(const vector<T> v) {
  cout << "[ ";
  F0R(i, v.size()) { cout << v[i] << ' '; }
  cout << "]" << '\n';
}

// 負の数にも対応した mod
// 例えば -17 を 5 で割った余りは本当は 3 (-17 ≡ 3 (mod. 5))
// しかし単に -17 % 5 では -2 になってしまう
inline long long mod(long long a, long long m) { return (a % m + m) % m; }

long long gcd(long long a, long long b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

/*  lcm (a, b) : 2整数版
    入力：整数 a, b
    出力：aとbの最小公倍数
*/
long long lcm(long long a, long long b) {
  long long d = gcd(a, b);
  return a / d * b;
}

// // Union-Find
// struct UnionFind {
//   vi par, siz;
//   // 初期化
//   UnionFind(int n) : par(n, -1), siz(n, -1) {}

//   // 根を求める
//   int root(int x) {
//     if (par[x] == -1)
//       return x;
//     else
//       return par[x] = root(par[x]);
//   }

//   // xとyが同じグループに属するか
//   bool issame(int x, int y) { return root(x) == root(y); }

//   // xのグループとyのグループを併合する
//   bool unite(int x, int y) {
//     x = root(x);
//     y = root(y);
//     if (x == y) return false;
//     if (siz[x] > siz[y]) swap(x, y);
//     par[y] = x;
//     siz[x] += siz[y];
//     return true;
//   }

//   // xのグループのサイズ
//   int size(int x) { return siz[root(x)]; }

// // 入力サンプル
// int N, M;
// cin >> N >> M;

// vpi Edge(M);
// for (int i = 0; i < M; i++) {
//   int a, b;
//   cin >> a >> b;
//   Edge[i].first = a - 1;
//   Edge[i].second = b - 1;
// }
// }
// ;

// // 深さ優先探索 再帰ver
// vector<bool> seen;
// void dfs(const Graph &G, int v) {
//   seen[v] = true;  // v を訪問済にする

//   // v から行ける各頂点 next_v について
//   for (auto next_v : G[v]) {
//     if (seen[next_v]) continue;  // next_v が探索済だったらスルー
//     dfs(G, next_v);              // 再帰的に探索
//   }
// }

// // 入力: グラフ G と，探索の始点 s
// // 出力: s から各頂点への最短路長を表す配列
// vector<int> bfs(const Graph &G, int s) {
//   int N = (int)G.size();    // 頂点数
//   vector<int> dist(N, -1);  // 全頂点を「未訪問」に初期化
//   queue<int> que;

//   // 初期条件 (頂点 s を初期頂点とする)
//   dist[s] = 0;
//   que.push(s);  // s を橙色頂点にする

//   // BFS 開始 (キューが空になるまで探索を行う)
//   while (!que.empty()) {
//     int v = que.front();  // キューから先頭頂点を取り出す
//     que.pop();

//     // v からたどれる頂点をすべて調べる
//     for (int x : G[v]) {
//       // すでに発見済みの頂点は探索しない
//       if (dist[x] != -1) continue;

//       // 新たな白色頂点 x について距離情報を更新してキューに挿入
//       dist[x] = dist[v] + 1;
//       que.push(x);
//     }
//   }
//   return dist;
// }

// // トポロジカルソート（幅優先）
// vector<int> topo_sort(const Graph &G) {  // bfs
//   vector<int> ans;
//   int n = (int)G.size();
//   vector<int> ind(n);            // ind[i]: 頂点iに入る辺の数(次数)
//   for (int i = 0; i < n; i++) {  // 次数を数えておく
//     for (auto e : G[i]) {
//       ind[e]++;
//     }
//   }
//   queue<int> que;
//   for (int i = 0; i < n; i++) {  // 次数が0の点をキューに入れる
//     if (ind[i] == 0) {
//       que.push(i);
//     }
//   }
//   while (!que.empty()) {  // 幅優先探索
//     int now = que.front();
//     ans.push_back(now);
//     que.pop();
//     for (auto e : G[now]) {
//       ind[e]--;
//       if (ind[e] == 0) {
//         que.push(e);
//       }
//     }
//   }
//   return ans;
// }

// --------------------------------------------------------
// This is tool
// --------------------------------------------------------

long long extGcd(long long a, long long b, long long &p, long long &q) {
  if (b == 0) {
    p = 1;
    q = 0;
    return a;
  }
  long long d = extGcd(b, a % b, q, p);
  q -= a / b * p;
  return d;
};

// 中国剰余定理
// リターン値を (r, m) とすると解は x ≡ r (mod. m)
// 解なしの場合は (0, -1) をリターン
pair<long long, long long> ChineseRem(const vector<long long> &b,
                                      const vector<long long> &m) {
  long long r = 0, M = 1;
  for (int i = 0; i < (int)b.size(); ++i) {
    long long p, q;
    long long d = extGcd(M, m[i], p, q);  // p is inv of M/d (mod. m[i]/d)
    if ((b[i] - r) % d != 0) return make_pair(0, -1);
    long long tmp = (b[i] - r) / d * p % (m[i] / d);
    r += M * tmp;
    M *= m[i] / d;
  }
  return make_pair(mod(r, M), M);
};

void Main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  vl x(3), y(3);
  F0R(i, 3) { cin >> x[i] >> y[i]; }

  pair<long long, long long> res = ChineseRem(x, y);
  if (res == make_pair(0 * 1LL, -1 * 1LL))
    cout << -1 << endl;
  else
    cout << res.first << endl;
  // cout << "x ≡ " << res.first << " (mod. " << res.second << ")" << endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
}

// わかりやすかったやつ
// https://atcoder.jp/contests/abc287/submissions/38502994
0