結果
問題 | No.187 中華風 (Hard) |
ユーザー |
|
提出日時 | 2024-03-22 02:00:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,828 bytes |
コンパイル時間 | 2,140 ms |
コンパイル使用メモリ | 199,904 KB |
最終ジャッジ日時 | 2025-02-20 10:50:22 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 WA * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long PreGarner(vector<long long> &B,vector<long long> &M,long long MOD){ long long ret = 1; for(int i=0; i<B.size(); i++) for(int k=i+1; k<B.size(); k++){ long long g = gcd(M.at(i),M.at(k)); if(B.at(i)%g != B.at(k)%g) return -1; M.at(i) /= g; M.at(k) /= g; long long g1 = gcd(M.at(i),g),g2 = g/g1; while(true){ g = gcd(g1,g2); if(g == 1) break; g1 *= g; g2 /= g; } M.at(i) *= g1,M.at(k) *= g2; B.at(i) %= M.at(i),B.at(k) %= M.at(k); } for(auto &m : M) ret = ret*m%MOD; return ret; //return lcm(m1,m2,...,mn). } long long extgcd(long long a, long long b, long long &x,long long &y){ if(b == 0){x = 1,y = 0; return a;} long long g = extgcd(b,a%b,y,x); y -= a/b*x; return g; } long long findinv(long long a,long long m){ long long x,y; extgcd(a,m,x,y); return (x%m+m)%m; } long long Garner(vector<long long> &B,vector<long long> &M,long long MOD){ M.push_back(MOD); vector<long long> mulM(M.size(),1),value(M.size(),0); for(int i=0; i<B.size(); i++){ long long t = (((B.at(i)-value.at(i))*findinv(mulM.at(i),M.at(i)))%M.at(i)+M.at(i))%M.at(i); for(int k=i+1; k<M.size(); k++){ value.at(k) = (value.at(k)+t*mulM.at(k))%M.at(k); mulM.at(k) = mulM.at(i)*M.at(i)%M.at(k); } } return value.back(); } int main(){ int N; cin >> N; vector<long long> B,M; bool allzero = true; while(N--){ int b,m; cin >> b >> m; if(b) allzero = false; B.push_back(b); M.push_back(m); } long long mod = 1e9+7; long long lcm = PreGarner(B,M,mod); if(lcm == -1 || allzero) cout << lcm << endl; else cout << Garner(B,M,mod) << endl; }