結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー ate
提出日時 2020-09-11 07:00:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 152 ms / 3,000 ms
コード長 2,521 bytes
コンパイル時間 2,239 ms
コンパイル使用メモリ 201,676 KB
最終ジャッジ日時 2025-01-14 09:30:32
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<tuple>
#include<cstdint>

template<class T = int64_t>
constexpr inline T mod(T a,T m){
  a %= m;
  return (a<0?a+m:a);
}

template<class T = int64_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};
}

template<class T = int64_t>
T mod_inv(T a,T m){
  auto[d,x,y] = ext_gcd(a,m);
  return (d!=1?-1:mod(x,m));
}

#include<vector>
#include<cassert>
#include<numeric>
#include<algorithm>

template<class T = int64_t>
T gerner(std::vector<T> const& b,std::vector<T> const& m){
  assert(0<std::size(b));
  assert(std::size(b)==std::size(m));
  T prod_m = 1;
  T x = b[0]%m[0];
  for(int i=1;i<std::size(b);++i){
    prod_m *= m[i-1];
    T mij = mod_inv(prod_m,m[i]);
    T t = mod((b[i]-x)*mij,m[i]);
    x += t*prod_m;
  }
  return x;
}

int64_t gerner (std::vector<int64_t> b,std::vector<int64_t> m,int64_t const MOD){
  using i64 = int64_t;
  assert(0<std::size(b));
  assert(std::size(b)==std::size(m));
  i64 sum_b = std::accumulate(std::begin(b),std::end(b),(i64)0,[](i64 acc,i64 bi){return acc+bi;});
  int n = std::size(b);
  // m を対ごとに素にする　無理なら -1
  for(int i=0;i+1<n;++i){
    for(int j=i+1;j<n;++j){
      i64 d = std::gcd(m[i],m[j]);
      if(sum_b>0 and (b[i]-b[j])%d!=0)return -1;
      m[i] /= d, m[j] /= d;
      i64 d0 = std::gcd(m[i],d);
      i64 d1 = d/d0;
      do{
        d = std::gcd(d0,d1);
        d0 *= d, d1 /= d;
      }while(d!=1);
      m[i] *= d0, m[j] *= d1;
      b[i] %= m[i], b[j] %= m[j];
    }
  }
  // x[i] が全て 0 なら y の　lcm を返す、y は対ごとに素なので掛けるだけでいい
  if(sum_b==0){
    i64 lcm_m = 1;
    for(i64 mi:m)(lcm_m*=mi)%=MOD;
    return lcm_m;
  }
  // gerner
  m.emplace_back(MOD);
  std::vector<i64> coeffs(std::size(m),1);
  std::vector<i64> constants(std::size(m),0);
  for(int k=0;k<n;++k){
    i64 m_inv = mod_inv(coeffs[k],m[k]);
    i64 t = mod((b[k]-constants[k])*m_inv,m[k]);
    for(int i=k+1;i<std::size(m);++i){
      (constants[i] += t*coeffs[i]) %= m[i];
      (coeffs[i] *= m[k]) %= m[i];
    }
  }
  return constants.back();
}

#include<bits/stdc++.h>

int64_t operator"" _i64(unsigned long long x){
  return (int64_t)x;
}

void solve_yuki_187(){
  using namespace std;
  using i64 = int64_t;
  constexpr i64 MOD = 1e9+7;

  int n;
  cin>>n;
  vector<i64> x(n),y(n);
  for(int i=0;i<n;++i)cin>>x[i]>>y[i];

  i64 ans = gerner(x,y,MOD);
  cout<< ans <<endl;
}

int main(){
  solve_yuki_187();
}
0