C++(g++ 7.5.0) 解法, 执行用时: 112ms, 内存消耗: 1996K, 提交时间: 2023-04-01 10:49:30

#include<bits/stdc++.h>
using namespace std;
#define int long long
int exgcd(int a, int b, int& x, int& y)
{
	if (b == 0)return x = 1, y = 0, a;
	int r = exgcd(b, a % b, x, y);
	tie(x, y) = make_tuple(y, x - a / b * y);
	return r;
}

int excrt(int n, int* r, int* m)
{
	int x = r[1], y1, y2, LCM = m[1];
	for (int i = 2;i<= n;i++)
	{
		int b = m[i], c = ((r[i] - x) % b + b) % b;
		int GCD = exgcd(LCM, b, y1, y2);
		if (c % GCD)return -1;//无解
		y1 = (__int128)y1 * (c / GCD) % (b / GCD);
		x += y1 * LCM;
		LCM *= b / GCD;
		x = (x % LCM + LCM) % LCM;
	}
	return x;
}
const int MAX = 1e5 + 10;
int r[MAX], m[MAX];
signed main()
{
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++)
		cin >> m[i] >> r[i];
	cout << excrt(n, r, m) << endl;
}

Python3 解法, 执行用时: 703ms, 内存消耗: 14872K, 提交时间: 2023-05-03 00:55:26

from math import *

def exgcd(a, b):
    if not b:
        return 1, 0, a

    y, x, g = exgcd(b, a % b)
    y = y - a // b * x
    return x, y, g

def excrt(n, r, p):
    now_p = p[0]
    now_r = r[0]

    for i in range(1, n):
        x, y, g = exgcd(now_p, p[i])
        if (r[i] - now_r) % g != 0:
            return -1
        now_r = x * (r[i] - now_r) // g * now_p + now_r
        now_p = lcm(now_p, p[i])
        now_r = now_r % now_p
    return now_r;


n = int(input())
r = []
p = []

for i in range(0, n):
    tmpp, tmpr = map(int, input().split(" "))
    r.append(tmpr)
    p.append(tmpp)

ans = excrt(n, r, p)
print(ans)

C++ 解法, 执行用时: 44ms, 内存消耗: 2048K, 提交时间: 2021-11-29 20:40:52

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define LL long long

const int N=100005;

LL ans,M,m[N],a[N];
int n;

LL exgcd(LL a,LL b,LL &x,LL &y)
{
	if (a%b==0) {x=0,y=1;return b;}
	LL d=exgcd(b,a%b,y,x);
	y-=(a/b)*x;return d;
}
int main()
{
	scanf("%d",&n);rep(i,1,n) scanf("%lld%lld",&m[i],&a[i]);
	ans=a[1],M=m[1];rep(i,2,n)
	{
		LL tM,b=a[i]-ans,x,y;
		LL g=exgcd(M,m[i],x,y);
		if (b%g) return puts("-1"),0;
		x=(__int128)x*b/g%m[i]; 
		tM=M,M=M/g*m[i],ans+=(__int128)tM*x%M;
	}
	printf("%lld\n",(ans%M+M)%M);
	return 0;
}