結果

問題 No.186 中華風 (Easy)
ユーザー ate
提出日時 2020-09-10 21:30:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,029 bytes
コンパイル時間 845 ms
コンパイル使用メモリ 80,688 KB
最終ジャッジ日時 2025-01-14 09:18:22
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<tuple>
#include<cassert>
#include<numeric>
#include<utility>
#include<vector>
#include<algorithm>

template<class T>
std::tuple<T,T,T> ext_gcd(T a,T b){
  if(b==0){
    return {a,1,0};
  }
  auto [d,y,x] = ext_gcd(b,a%b);
  y -= a/b * x;
  return {d,x,y};
}

/*
https://qiita.com/drken/items/ae02240cd1f8edfc86fd
  x \equiv b_1 (mod. m_1)
  x \equiv b_2 (mod. m_2)
  を満たす x が存在する必要十分条件は
  b_1 \equiv b_2 (mod. gcd(m_1,m_2))
  これを満たす x が 0 <= x < lcm(m_1,m_2)に存在する
x の構成方法
  m_1*p + m_2*q = gcd(m_1,m_2)
  を満たす(p,q)をextended gcdより得る
  b_1 \equiv b_2 (mod. gcd(m_1,m_2))より、
  (b_2-b_1) % gcd(m_1,_m2) == 0
  d = gcd(m_1,m_2)
  s = (b_2-b_1)/d
  とおくと、
  s*m_1*p + s*m_2*q = b_2-b_1
  となる。ここで、
  x = b_1+s*m_1*p = b_2-s*m_2*q
  とおくと、
  x \equiv b_1 (mod. m_1)
  x \equiv b_2 (mod. m_2)
  が成り立つ
*/
template<class T>
std::pair<T,T> crt1(T b1,T m1,T b2,T m2){
  auto [d,p,q] = ext_gcd(m1,m2);
  if((b2-b1)%d)return {0,-1};
  T lcm_m = m1/d*m2;
  T s = (b2-b1)/d;
  T x = b1+s*m1*p;
  return {x,lcm_m};
}

template<class T>
std::pair<T,T> crt(std::vector<T> const& b,std::vector<T> const& m){
  assert(std::size(b)==std::size(m));
  T r = 0, lcm_m = 1;
  for(int i=0;i<std::size(b);++i){
    auto& b_i = b[i], m_i = m[i];
    auto [d,p,q] = ext_gcd(lcm_m,m_i);
    if((b_i-r)%d)return {-1,-1};
    T s = (b_i-r)/d;
    T tmp = s*p%(m_i/d);
    r += lcm_m*tmp;
    lcm_m *= m_i/d;
  }
  r = (r%lcm_m+lcm_m)%lcm_m;
  return {r,lcm_m};
}

void solve(){
  using namespace std;
  int n = 3;
  vector<int64_t> b(n),m(n);
  for(int i=0;i<n;++i)cin>>b[i]>>m[i];
  if(std::all_of(std::begin(b),std::end(b),[](auto bi){return bi==0;})){
    std::cout<< std::accumulate(std::begin(m),std::end(m),1ll,[](int64_t x,int64_t mi){return std::lcm(x,mi);}) <<std::endl;
    return ;
  }
  auto [x,mod] = crt(b,m);
  cout<<x<<endl;
}

int main(){
  int t = 1;
  while(t--){
    solve();
  }
}
0