結果

問題 No.186 中華風 (Easy)
ユーザー Dispersion-atc
提出日時 2024-12-12 13:47:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,083 bytes
コンパイル時間 3,231 ms
コンパイル使用メモリ 248,668 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-12 13:47:48
合計ジャッジ時間 4,502 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #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 if
using 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/447
void 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);
if(r == 0) r = m;
cout << r << '\n';
return;
}
int main() {
solve1();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0