結果
問題 |
No.187 中華風 (Hard)
|
ユーザー |
![]() |
提出日時 | 2025-03-18 19:37:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 84 ms / 3,000 ms |
コード長 | 1,057 bytes |
コンパイル時間 | 2,144 ms |
コンパイル使用メモリ | 201,044 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-18 19:37:56 |
合計ジャッジ時間 | 4,405 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include<bits/stdc++.h> using namespace std; int modinv(int a,int m){ a%=m; if((a-1)%m==0)return a; return(1-(long)m*modinv(m,a))/a; } pair<int,int>crt_mod(vector<int>r,vector<int>m,int mod){ int n=r.size(); assert(m.size()==n); for(int i=1;i<n;i++)for(int j=0;j<i;j++){ int g=gcd(m[i],m[j]); if((r[i]-r[j])%g)return{0,0}; if(g==1)continue; m[i]/=g,m[j]/=g; int gi=gcd(m[i],g),gj=g/gi; do{g=gcd(gi,gj),gi*=g,gj/=g;}while(g!=1); m[i]*=gi,m[j]*=gj; assert(gcd(m[i],m[j])==1); r[i]%=m[i],r[j]%=m[j]; } m.push_back(mod); vector<int>x(n+1),p(n+1,1); for(int i=0;i<n;i++){ int k=long(r[i]-x[i])%m[i]*modinv(p[i],m[i])%m[i]; if(k<0)k+=m[i]; assert(0<=k&&k<m[i]); for(int j=i+1;j<=n;j++){ x[j]=(x[j]+(long)k*p[j]%m[j])%m[j]; p[j]=(long)p[j]*m[i]%m[j]; } } return{x[n],p[n]}; } int main(){ int n; cin>>n; vector<int>r(n),m(n); for(int i=0;i<n;i++)cin>>r[i]>>m[i]; auto[x,l]=crt_mod(r,m,1000000007); if(l==0){cout<<-1<<'\n';return 0;} bool zero=1; for(int i=0;i<n;i++)if(r[i]>0)zero=0; cout<<(zero?l:x)<<'\n'; }