解題關鍵：注意爆long long

$x \equiv {M_1}M_1^{ - 1}{a_1} + ... + {M_k}M_k^{ - 1}{a_k}(\bmod m)$

其中，$m = \prod\limits_{j = 1}^k {{m_j}}$，$\forall 1 \le j \le k$，${M_j} = \frac{m}{{{m_j}}}$，$M_j^{ - 1}$是滿足${M_j}M_j^{ - 1} \equiv 1(\bmod m)$的一個整數(shù)

復雜度$O(n\log n)$

?

?

1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll a[100],b[100]; 5 ll x,y; 6 ll extgcd(ll a,ll b,ll &x,ll &y){ 7 int d=a; 8 if(b){ 9 d=extgcd(b,a%b,y,x); 10 y-=a/b*x; 11 }else{ 12 x=1,y=0; 13 } 14 return d; 15 } 16 int main(){ 17 ll n,m=1; 18 ll ans=0; 19 cin>>n; 20 for(int i=0;i<n;i++){ cin>>b[i]>>a[i];m*=b[i];} 21 for(int i=0;i<n;i++){ 22 ll mi=m/b[i]; 23 extgcd(mi,b[i],x,y); 24 x=(x+b[i])%b[i]; 25 ans=(ans+mi*x*a[i]+m)%m; 26 } 27 cout<<ans<<endl; 28 return 0; 29 }

?

轉載于:https://www.cnblogs.com/elpsycongroo/p/6914070.html

總結

以上是生活随笔為你收集整理的[51nod1079]中国剩余定理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。