204. 表达整数的奇怪方式
给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai)。
输入格式
第 1 行包含整数 n。
第 2…n+1 行：每 i+1 行包含两个整数 ai 和 mi，数之间用空格隔开。
输出格式
输出最小非负整数 x，如果 x 不存在，则输出 −1。
如果存在 x，则数据保证 x 一定在 64 位整数范围内。
数据范围
1≤ai≤231−1,
0≤mi<ai
1≤n≤25
输入样例：
2
8 7
11 9
输出样例：
31
分析及代码：
1. 将式子等价转换
对于每两个式子（我们考虑将其合并）：
x≡m1(% a1)
x≡m2(% a2)
则有：
x=k1∗a1+m1
x=k2∗a2+m2
进一步：
k1∗a1+m1=k2∗a2+m2
移项：
k1∗a1−k2∗a2=m2−m1
也就是：
① k1∗a1+k2∗(−a2)=m2−m1
也就是我们需要找到一个最小的k1,k2，使得等式成立（因为要求x最小，而a和m都是正数）。
2. 用扩展欧几里得算法找出一组解
我们已知a1,m1,a2,m2，可以用扩展欧几里得算法算出一个k1′,k2′使得：
k′1∗a1+k′2∗(−a2)=gcd(a1,−a2)
无解判断：
若gcd(a1,−a2)∤m2−m1，则无解。
我们设d=gcd(a1,−a2),y=(m2−m1)/d
承接上文，我们只需让k1,k2分别扩大y倍，则可以找到一个k1,k2满足①式：
k1=k′1∗y,k2=k′2∗y
3. 找到最小正整数解
我们知道一个性质：
②k1=k1+k∗a2/d
k2=k2+k∗a1/d
k为任意整数，这时新的k1,k2仍满足①式。
######## 证明：
将新的k1,k2带入式子得:
(k1+k∗a2/d)∗a1+(k2+k∗a1/d)∗(−a2)=m2−m1
拆出来：
k1∗a1+k∗a2∗a1/d+k2∗(−a2)+k∗a1∗(−a2)/d=m2−m1
交换一下顺序，把负号拆出来：
k1∗a1+k2∗(−a2)+k∗a2∗a1/d−k∗a1∗a2/d=m2−m1
那个同加同减可以消掉：
k1∗a1+k2∗(−a2)=m2−m1
这个式子和①是一样的，因①成立，故此式也成立。
要找一个最小的非负整数解，我们只需要让
k1=k1% abs(a2/d)
k2=k2% abs(a1/d)
即可找到当前最小的k1,k2的解，即此时的k为0。
Q：此处为什么要取绝对值呢
A：因为不知道a2/d的正负性，我们在原基础上要尽量减多个abs(a2/d)，使其为正整数且最小。
4. 等效替代：
由②式带入
新的x为：
x=(k1+k∗a2/d)∗a1+m1
=k1∗a1+m1+k∗a2∗a1/d
=k1∗a1+m1+k∗lcm(a1,a2) ③
Q:这里，k都为0了，为什么还要算呢？
A:因为这只是前两个式子得最小k，有可能遇到下一个式子后面*要扩大
在③中，我们设a0=lcm(a1,a2),m0=k1∗a1+m1
那么：
③ =k∗a0+m0
这个形式与一开始我们分解的形式是不是特别像呢？
没错！假设之后又来了一个a3,m3
我们只需要继续找：
x=k∗a0+m0=k3∗(−a3)+m3，那么问题又回到了第一步。
5. 总结
我们的做法相当于每次考虑合并两个式子，将这n个式子合并n−1次后变为一个式子。最后剩下的式子就满足我们的答案。
注意：
- lcm(a1,a2)和%a2/d，需要取绝对值。又因为d=gcd(a1,−a2)，我们不知道a1的正负性（可能是上一步推过来的）。
- %a2/d，需要取绝对值， 膜负数的话，不会取到正解；
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL extend_gcd(LL a, LL b, LL &x, LL &y)
{
if (!b)
{
x = 1;
y = 0;
return a;
}
LL r = extend_gcd(b, a % b, x, y);
LL temp = x;
x = y;
y = temp - a / b * y;
return r;
}
LL mod(LL a, LL b)
{
return ((a % b) + b) % b;
}
int main()
{
int n;
cin >> n;
LL x = 0, m1, a1;
cin >> a1 >> m1;
for (int i = 0; i < n - 1; i++)
{
LL m2, a2;
cin >> a2 >> m2;
LL k1, k2;
LL d = extend_gcd(a1, -a2, k1, k2);
if ((m2 - m1) % d)
{
puts("-1");
return 0;
}
k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d));
m1 = k1 * a1 + m1;
a1 = abs(a1 / d * a2); // lcm
}
printf("%lld\n", m1);
return 0;
}