結果
問題 | No.186 中華風 (Easy) |
ユーザー |
|
提出日時 | 2024-12-12 13:46:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,063 bytes |
コンパイル時間 | 3,196 ms |
コンパイル使用メモリ | 247,904 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-12 13:46:14 |
合計ジャッジ時間 | 4,176 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 WA * 2 |
ソースコード
// #include "../../merge_src_docs/template/24_template.hpp"#include <bits/stdc++.h>using namespace std;using ll = long long;#define rep(i, n) for(ll i = 0; i < n; i++)#define rep2(i, l, r) for(ll i = l; i < r; i++)using vi = vector<int>;using vvi = vector<vi>;using vll = vector<ll>;#define all(A) A.begin(), A.end()#define elif else ifusing pii = pair<ll, ll>;bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }struct IOSetup {IOSetup() {cin.tie(0);ios::sync_with_stdio(0);}} iosetup;template<class T>void print(vector<T> a) {for(auto x : a) cout << x << ' ';cout << endl;}void print(auto x) { cout << x << endl; }template<class Head, class... Tail>void print(Head &&head, Tail &&...tail) {cout << head << ' ';print(forward<Tail>(tail)...);}//#include "../../merge_src_docs/math/crt.hpp"/*- `extgcd(ll a, ll b, ll &x, ll &y)` : `ax + by = gcd(a, b)` を満たす `x, y` を格納する.`|x| + |y|` は最小化されるらしい- `pair<ll, ll> crt(vll &r, vll &m)` : `x = r[i] (mod m[i])` を解く.解が存在しないなら `{-1, -1}`, 存在するなら `{x, lcm(m[1], m[2], ...)}` を返す.*/ll extgcd(ll a, ll b, ll &x, ll &y) {// assert(a >= 0 && b >= 0);if(!b) return x = 1, y = 0, a;ll d = extgcd(b, a % b, y, x);y -= a / b * x;return d;}ll inv_mod(ll x, ll m) {ll y, z;extgcd(x, m, y, z);return (y % m + m) % m;}pair<ll, ll> crt(vll r, vll m) {int n = r.size();ll r0 = 0, m0 = 1;rep(i, n) {ll g, im, x;g = extgcd(m0, m[i], im, x);if((r[i] - r0) % g) return {-1, -1};ll tmp = (r[i] - r0) / g * im % (m[i] / g);r0 += m0 * tmp;m0 *= m[i] / g;}return {(r0 % m0 + m0) % m0, m0};}// https://yukicoder.me/problems/447void solve1() {vector<ll> X(3), Y(3);rep(i, 3) {ll x, y; cin >> x >> y;X[i] = x, Y[i] = y;}auto [r, m] = crt(X, Y);cout << r << '\n';return;}int main() {solve1();return 0;}