P4777 【模板】扩展中国剩余定理（EXCRT）

题目描述

给定 n 组非负整数 ai​,bi​ ，求解关于 x 的方程组的最小非负整数解。

x≡b1​ (mod a1​)

x≡b2​ (mod a2​).

x≡bn​ (mod an​)​

输入格式

输入第一行包含整数 n。

接下来 n 行，每行两个非负整数 ai​,bi​。

输出格式

输出一行，为满足条件的最小非负整数 x。

输入输出样例

输入 #1复制

3
11 6
25 9
33 17

输出 #1复制

809

说明/提示

对于 100% 的数据，1≤n≤105，1≤bi​,ai​≤1012，保证所有 ai​ 的最小公倍数不超过 10181018。

请注意程序运行过程中进行乘法运算时结果可能有溢出的风险。

数据保证有解。

解析：

中国剩余定理扩展：

当mi他们两两不互质的时候，x  = a*q1 + r1 , x = b*q1 + r2;

a*q1 + r1 = b* q2 + r2  移项可得 a*q1 + b*q2 =  r2 - r1

由裴蜀定理 ：

当 gcd(a,b) | r2 - r1  则有解，否则无解 。

这时我们可以利用扩展的欧拉定理求解 特解 ：q1   = p * (r2 - r1) /gcd(a,b)

并对其求通解： P = q1 + b / gcd(a ,b )*K  (K为任意常数)

编程思路：

第一个方程我们只需要记录 其 摩数 和 余项

对后后面的方程进行 合并：extend_gcd(a, b, x, y);

扩张欧几里得代码：

ll extend_gcd(ll a, ll b, ll& x, ll& y) {
	if (b == 0) { x = 1; y = 0; return a; }
	ll d = extend_gcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

求出了 当前合并的 m 和 下个 mi的 最大公倍数和 （ax+by = 1）中x的值 

然后求 通项：x = x*c /d; 因为x 可以扩大 mi /d 配 所以直接加即可。

ans = a1 + x*m1 相当于 r1 + xxxx

代码如下 ：

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
ll ai[N], mi[N];
ll extend_gcd(ll a, ll b, ll& x, ll& y) {
	if (b == 0) { x = 1; y = 0; return a; }
	ll d = extend_gcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
ll excrt() {
	ll x, y;
	ll m1 = mi[1], a1 = ai[1];
	ll ans = 0; 
	//r = m1*p + r1
	for (int i = 2; i <= n; i++) {
		ll a2 = ai[i], m2 = mi[i];
		ll a = m1, b = m2, c = (a1 - a2); 
		ll d = extend_gcd(a, b, x, y);
		if ( c % d != 0) return -1;
		x = x*c/d;
		x = (x%(m2/d) + m2/d) % (m2 /d);
		ans = a1 + x * m1;
		m1 = m2 / d * m1; // lcm   
		ans = (ans % m1 + m1) % m1;//保证为 正整数  
		a1 = ans;
	}
	return ans;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> mi[i] >> ai[i];
	cout << excrt();
	return 0;
}

时间复杂度为：O（n * 扩展欧几里得算法）