题目描述：
给定2n个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数x，满足?i∈[1,n],x≡mi(mod ai)。
输入格式
第1行包含整数n。第2..n行：每i+1行包含两个整数ai和mi,数之间用空格隔开。
输出格式
输出最小非负整数x，如果x不存在，则输出-1。如果存在x，则数据保证x一定在64位整数范围内。
数据范围
1≤ai≤2^31?1,0≤mi 输入样例：
2
8 7
11 9
输出样例：
31
分析：
首先，介绍下中国剩余定理。中国剩余定理给出了以下的一元线性同余方程组：
文章图片
有解的判定条件，并用构造法给出了在有解情况下解的具体形式。中国剩余定理说明：假设整数m1,m2, ... ,mn两两互质，则对任意的整数：a1,a2, ... ,an，方程组S有解，并且通解可以用如下方式构造得到：设
文章图片
是整数m1,m2, ... ,mn的乘积，并设
文章图片
是除了mi以外的n- 1个整数的乘积。
设
文章图片
为Mi模mi的乘法逆元，
文章图片
则方程组S的通解形式为
文章图片
在模M的意义下，方程组S只有一个解：
文章图片
证明：
从假设可知，对任何
文章图片
，由于
文章图片
，所以
文章图片
这说明存在整数ti使得
文章图片
（变换得tiMi + miy = 1，gcd（mi,MI）=1，故有解）。 也就是说正因为mi，mj互质，才保证了Mi模mi乘法逆元ti的存在。
对于aitiMi而言，
文章图片
又
文章图片
因为Mi是mj的倍数
所以
文章图片
满足：
文章图片
即x就是方程组S的一个解。
另外，假设x1和x2都是S的解，则
文章图片
而m1,m2,...,mn两两互质，故x1-x2被mi（i从1到n）整除，即
文章图片
整除x1 - x2.所以S的任意两个解之间必然相差M的整数倍，另一方面，
文章图片
是一个解，同时所有形式为：
文章图片
的整数也是方程组S的解，所以方程组所有的解的集合就是：
文章图片
对本题而言，要求x≡mi(mod ai)的最小非负整数解（注意这里ai和mi的含义与上面证明反过来了），由于没有ai,aj互质的条件，故不能保证乘法逆元的存在，所以需要重新求解。由x≡mi(mod ai)推出x = k1a1 + m1,x = k2a2 + m2。故k1a1 - k2a2 = m2 - m1，当gcd(a1,-a2) | m2 - m1时，前两个方程构成的方程组有解。同样，我们用扩展欧几里得算法来求解k1a1 - k2a2 = gcd(a1,-a2) = d的解后，乘上(m2 - m1) / d即可得到k1和k2真正的解。令k1=k1+k?a2/d，k2=k2+k?a1/d代入前面的方程发现依旧满足，所以我们得到了k1和k2的一组解，x = (k1+k*a2/d)a1 + m1=k1a1+m1+ka1a2/d=k1a1+m1+klcm(a1,a2)，令m = k1a1 + k2a2,a=lcm(a1,a2)就可以得到新的方程x=ka+m了，再与第三个方程继续这样求，直到剩下最后一个方程为止，此时，x=k1a1+m1，x取最小非负整数，则k1应该取k1 % (k*a2/d)，此时k1最小，x也最小。
#include
#include
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x = 1,y = 0;
return a;
}
ll d = exgcd(b,a % b,y,x);
y -= a / b * x;
return d;
}
int main(){
int n;
cin>>n;
ll x = 0,m1,a1,m2,a2,k1,k2;
cin>>a1>>m1;
for(int i = 0;
i < n - 1;
i++){
cin>>a2>>m2;
ll d = exgcd(a1,-a2,k1,k2);
if((m2 - m1) % d){
x = -1;
break;
}
k1 *= (m2 - m1) / d;
k1 = (k1 % (a2 / d) + a2 / d) % (a2 / d);
x = k1 * a1 + m1;
ll a = abs(a1 / d * a2);
m1 = k1 * a1 + m1;
a1 = a;
}
if(x != -1) x = (x % a1 + a1) % a1;
cout< 【算法基础课|AcWing 204 表达整数的奇怪方式】
推荐阅读
- 算法基础课|AcWing 875 快速幂
- 概率期望|LightOJ - 1030 Discovering Gold 期望 DP
- 备战蓝桥杯|【蓝桥python冲刺31天】——拿下数论，冲进国赛
- #|椭圆曲线（椭圆曲线是怎么来的（））
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题