結果

問題 No.2117 中国剰余定理入門
コンテスト
ユーザー shkiiii_
提出日時 2022-11-04 21:42:05
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,261 bytes
コンパイル時間 1,571 ms
コンパイル使用メモリ 170,072 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 19:25:03
合計ジャッジ時間 2,261 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
// #include<atcoder/all>
// #include<boost/multiprecision/cpp_int.hpp>

using namespace std;
// using namespace atcoder;
// using bint = boost::multiprecision::cpp_int;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
// #define MOD 1000000007
#define MOD 998244353

long long ext_gcd(long long a,long long b,long long &p,long long &q){
  if(b == 0){
    p = 1;q = 0;
    return a;
  }
  long long d = ext_gcd(b,a%b,p,q);
  long long x = p-(a/b)*q;
  p = q;q = x;
  return d;
}

pair<long long,long long> crt(const vector<long long> &b,const vector<long long> &m){
  long long r = 0,M = 1;
  for(int i = 0;i < b.size();i++){
    long long p,q;
    long long d = ext_gcd(M,m[i],p,q);
    if((b[i]-r)%d != 0)return make_pair(0,0);
    long long tmp = (b[i]-r)/d*p%(m[i]/d);
    r += M*tmp;
    M *= m[i]/d;
  }
  return make_pair((r%M+M)%M,M);
}

int main(){
  
  vector<ll> b(2),c(2);
  rep(i,2)cin >> b[i] >> c[i];
  if((c[1]-c[0])%__gcd(b[0],b[1]) != 0){
    cout << "NaN\n";
    return 0;
  }
  c[0] = (c[0]%b[0] + b[0])%b[0];
  c[1] = (c[1]%b[1] + b[1])%b[1];
  P k = crt(c,b);
  cout << k.first << "\n";
  

  return 0;
}
0