結果
| 問題 |
No.186 中華風 (Easy)
|
| コンテスト | |
| ユーザー |
 kenseitogari
|
| 提出日時 | 2023-02-04 13:00:22 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,340 bytes |
| コンパイル時間 | 3,642 ms |
| コンパイル使用メモリ | 174,392 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-07-03 10:54:45 |
| 合計ジャッジ時間 | 4,457 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 23 |
ソースコード
#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.first == 0 && res.second == -1)
cout << -1 << endl;
else if (res.first == 0)
cout << res.first + res.second << 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