首页 > 代码库 > [51nod1079]中国剩余定理
[51nod1079]中国剩余定理
解题关键：注意爆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)$的一个整数
复杂度$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 }
[51nod1079]中国剩余定理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。