結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー Rumain831
提出日時 2026-11-04 04:07:59
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc16.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,588 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,078 ms
コンパイル使用メモリ 181,548 KB
実行使用メモリ 7,860 KB
最終ジャッジ日時 2026-11-04 04:08:04
合計ジャッジ時間 4,257 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge7_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;

ll extgcd(ll a, ll b, ll& x, ll& y){
  if(b==0){
    x=1, y=0; return a;
  }
  ll x1, y1;
  ll gcd=extgcd(b, a%b, x1, y1);
  x=y1; y=x1-(a/b)*y1;
  return gcd;
}

//ax≡b mod m (0, -1):解なし, (0, 1):任意
pair<ll, ll> crt1(ll a, ll b, ll m){
  if(m==0) return {0, -1};
  b=(b%m+m)%m;
  if(a==0) return (b==0?make_pair(0, 1):make_pair(0, -1));
  ll x, y, g=extgcd(a, m, x, y);
  if(b%g) return {0, -1};
  a/=g, b/=g, m/=g;
  extgcd(a, m, x, y);
  ll r=b*x%m; r=(r+m)%m;
  return make_pair(r, m);
}

//ax≡b mod m1, cx≡d mod m2
pair<ll, ll> crt2(ll a, ll b, ll m1, ll c, ll d, ll m2){
  auto [r1, n1]=crt1(a, b, m1); // x≡r1 mod n1
  auto [r2, n2]=crt1(c, d, m2); // x≡r2 mod n2
  if(n1==-1||n2==-1) return {0, -1};
  r1=(r1%n1+n1)%n1, r2=(r2%n2+n2)%n2;
  if(n1==1) return {r2, n2};
  if(n2==1) return {r1, n1};
  ll x, y;
  ll g=extgcd(n1, n2, x, y);
  if(r1%g!=r2%g) return {0, -1};
  ll D=(r2-r1)/g;
  ll n2g=n2/g, inv=(x%n2g+n2g)%n2g;
  ll t=(ll)((__int128)D*inv%n2g); t=(t+n2g)%n2g;
  __int128 lcm=(__int128)(n1/g)*n2;
  __int128 ans=r1+(__int128)n1*t; ans=((ans%lcm)+lcm)%lcm;
  return {ans, lcm};
}


int main(void){
  ll x[3], y[3];
  for(int i=0; i<3; i++) cin >> x[i] >> y[i];
  auto [p1, m1]=crt2(1, x[0], y[0], 1, x[1], y[1]);
  if(m1==-1){
    cout << -1 << endl; return 0;
  }
  auto [p2, m2]=crt2(1, p1, m1, 1, x[2], y[2]);
  if(m2==-1){
    cout << -1 << endl; return 0;
  }
  if(m2==1){
    cout << 1 << endl; return 0;
  }
  cout << p2 << endl;
  return 0; 
}
0