- #include<stdio.h>
- #define ll long long
- /*
- gcd(a,b) = Xa+Yb
- Xb+Y(a%b) = Xb + Y( a - a/b*b ) = Xb + Ya - a/b*Y*b = Ya + (X-a/b*Y)b
- */
- ll x,y;
- void exgcd(ll a,ll b){
- if( a%b==0 ){
- x = 0;
- y = 1;
- }
- else{
- exgcd(b,a%b);
- ll temp = x;
- x = y;
- y = temp - a/b*y;
- }
- }
- ll N=1,ans;
- int k[15],p[15];
- int main(){
- int n; scanf("%d",&n);
- for(int i=1;i<=n;i++){
- scanf("%d%d",p+i,k+i);
- N*=p[i];
- }
- for(int i=1;i<=n;i++){
- /*p[i] 与 N/p[i] 互质
- gcd(p[i],N/p[i]) = 1
- X*p[i] + Y*N/p[i] = 1
- Y 是 N/p[i] 模 p[i] 下的乘法逆元
- */
- exgcd(p[i],N/p[i]);
- //cout<<x<<""<<p[i]<<" "<<y<<" "<<N/p[i]<<endl;
- ans = (ans + k[i]*N/p[i]*y)%N;
- }
- printf("%lld",(ans % N + N) % N);
- }
来源: http://www.bubuko.com/infodetail-3277472.html