結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー fu2tian2
提出日時 2021-02-28 11:59:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,969 bytes
コンパイル時間 2,004 ms
コンパイル使用メモリ 198,776 KB
最終ジャッジ日時 2025-01-19 08:06:30
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //int:2*10**9
typedef long double ld;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define vec2(name,i,j,k) vector<vector<ll>> name(i,vector<ll>(j,k))
#define vec3(name,i,j,k,l) vector<vector<vector<ll>>> name(i,vector<vector<ll>>(j,vector<ll>(k,l)))
#define pb push_back
#define MOD 1000000007 //998244353
#define PI 3.141592653
#define INF 8000000000000000000 //14
//cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
ll mod(ll x, ll y) {
    if (x<0) x+=(abs(x)/y)*y+y;
    return x%y;
}

vector<ll> crt1(ll x, ll y) {
    // x*s-y*t=gcd(x,y)となるs,t,gcdを返す
    // cout << "test1 " << x << " " << y << endl;
    if (x%y==0) return {1,x/y-1,y};
    auto v = crt1(y,x%y);
    ll s = mod(-v[1],y/v[2]);
    ll t = (x*s-v[2])/y;
    // cout << "test2 " << x << " " << y << " " << s << " " << t << endl;
    return {s,t,v[2]};
}

P crt2(ll a, ll b, ll c, ll d) {
    // a mod bかつ、c mod dとなるval mod(lcm(b,d))
    if (abs(c-a)%__gcd(b,d)!=0) return {INF,-1};
    if (b<d) {swap(b,d); swap(a,c);}
    auto v = crt1(b,d);
    ll val = mod(v[0]*((c-a)/v[2]),d);
    val = val*b+a;
    ll lcm = b*d/v[2];
    // cout << "test" << " " << val << endl;
    val = mod(val,lcm);
    return {val,lcm};
}
P crt(vector<ll> rem, vector<ll> div) {
    // CRT(crt2のn個拡張版)
    ll x = 0; ll y = 1; P v;
    REP(i,rem.size()) {
        if (y<div[i]) {swap(x,rem[i]); swap(y,div[i]);}
        v = crt2(x,y,rem[i],div[i]);
        // cout << i << " " << v.first << " " << v.second << endl;
        if (v.second==-1) return {-1,-1};
        x = v.first; y = v.second;
    }
    return v;
}

int main(){
    vector<ll> x(3); vector<ll> y(3);
    REP(i,3) cin >> x[i] >> y[i];
    auto v = crt(x,y);
    if (v.first!=0) cout << v.first << endl;
    else cout << v.second << endl;
}
0