C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 484K, 提交时间: 2022-08-05 19:27:08

#include<bits/stdc++.h>
using namespace std;
#define N 20
#define ll long long
ll n,x,y,ans;
ll a[N],m[N];
inline ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    ll ret=exgcd(b,a%b,x,y);
    ll t=x;x=y,y=t-(a/b)*y;
    return ret;
}
inline ll China(ll n)
{
    ll ans=0,M=1;
    for(ll i=1;i<=n;i++)M*=m[i];
    for(ll i=1;i<=n;i++)
    {
        ll Mi=M/m[i];
        exgcd(Mi,m[i],x,y);
        ans=(ans+x*a[i]*Mi)%M;
    }
    if(ans<0)ans+=M;
    return ans;
} 
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        scanf("%lld%lld",&m[i],&a[i]);
    ans=China(n);
    printf("%lld\n",ans);
    return 0;
}

C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2020-11-09 07:57:24

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
int a[12],b[12];
int n,Ans = 0;
int sum = 1;
int Mod ;
signed main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)cin >> a[i] >> b[i];
    for(int i = 1 ; i <= n ; i ++)sum *= a[i],Mod = sum;
    for(int i = 1 ; i <= n ; i ++)
    {
        if(a[i] == 1)continue;
        int t = sum / a[i],A=t;
        while(A % a[i] != 1)A += t;
        Ans = Ans + (A * b[i]) % Mod;
        Ans %= Mod;
    }
    cout << Ans % Mod;
    return 0;
}

Python3 解法, 执行用时: 49ms, 内存消耗: 4608K, 提交时间: 2023-05-27 10:30:27

def Exgcd(a,b):
    if b==0:
        return 1,0,a
    else:
        x,y,d=Exgcd(b,a%b)
        x,y=y,(x-(a//b)*y)
        return x,y,d
    
a=[]
b=[]
n=int(input())
M=1
ans=0
for i in range(n):
    x,y=map(int,input().split())
    M*=x
    a.append(x)
    b.append(y)
for i in range(n):
    mi=M//a[i]
    x,y,d=Exgcd(mi,a[i])
    ans+=mi*b[i]*x%M
    ans%=M
print(ans%M)