点击查看代码
#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;
}
LL inline mod(LL a, LL b)
{
return ((a % b) + b) % b;
}
int main()
{
int n;
cin >> n;
LL a1, m1;
cin >> a1 >> m1;
bool has_answer = true;
for (int i = 0; i < n - 1; i ++) {
LL a2, m2;
cin >> a2 >> m2;
LL k1, k2;
LL d = exgcd(a1, a2, k1, k2);
if ((m2 - m1) % d) {
has_answer = false;
break;
}
k1 *= (m2 - m1) / d;
LL t = a2 / d;
k1 = mod(k1, t);
m1 = a1 * k1 + m1;
a1 = abs(a1 / d * a2); // 最小公倍数
}
if (has_answer) {
cout << mod(m1, a1) << endl;
}
else puts("-1");
return 0;
}
- 扩展中国剩余定理
① 对于每两个式子 $ x \equiv m_1 ( \bmod a_1) $ ，$ x \equiv m_2 ( \bmod a_2) $ ，可以写成 $ x = k_1 \cdot a_1 + m_1 $ ，$ x = k_2 \cdot a_2 + m_2 $ ，右边两个式子都等于 $ x $ ，可以得到 $ k_1 \cdot a_1 + m_1 = k_2 \cdot a_2 + m_2 $ ，整理得到 $ k_1 \cdot a_1 + k_2 \cdot (- a_2) = m_2 - m_1 $
② 使用扩展欧几里得算法可得到 $ k_1', k_2' $ ，使得 $ k_1' \cdot a_1 + k_2' \cdot a_2 = gcd(a_1, -a_2) $ ， 若 $ m_2 - m_1 $ 不是 $ gcd(a_1, -a_2) $ 的倍数，则说明无解；否则，记 $ gcd(a_1, -a_2) $ 为 $ d $ ，那么 $ k_1, k_2 $ 可用 $ k_1', k_2' $ 表示为：$ k_1 = \frac{m_2 - m_1}{d} \cdot k_1' $ ，$ k_2 = \frac{m_2 - m_1}{d} \cdot k_2' $
③ 让 $ k_1 = k_1 + k \cdot \frac{a_2}{d} $ ，$ k_2 = k_2 + k \cdot \frac{a_1}{d} $ ，在 $ k $ 取任意值时，代入 $ k_1 \cdot a_1 + k_2 \cdot (- a_2) = m_2 - m_1 $ 可以发现新的 $ k_1 , \ k_2 $ 仍然满足等式，也就是说已经找到 $ k_1 , \ k_2 $ 的通解公式，要找一个最小的非负整数 $ x $ ，只需让 $ k_1 = k_1 \bmod \left | \frac{a_2}{d} \right | , \ k_2 = k_2 \bmod \left | \frac{a_1}{d} \right | $ ，即可找到最小的 $ k_1 , \ k_2 $ 的解
④ 将 $ k_1 = k_1 + k \cdot \frac{a_2}{d} $ 代入 $ x = k_1 \cdot a_1 + m_1 $ 中，可得 $ x = (k_1 + k \cdot \frac{a_2}{d}) \cdot a_1 + m_1 = k_1 \cdot a_1 + m_1 + k \cdot \frac{a_1 \cdot a_2}{d} = k_1 \cdot a_1 + m_1 + k \cdot lcm(a_1, a_2) $ ，令 $ a_0 = lcm(a_1, a_2) , \ m_0 = k_1 \cdot a_1 + m_1 $ ，那么 $ x = k \cdot a_0 + m_0 $ ，至此，完成了前两个方程的合并，再用新得到的方程和 $ x = k_3 \cdot a_3 + m_3 $ 合并，以此类推，就可以把所有的方程合并，最后得到一个式子 $ x = k \cdot a + m $ ，最小正整数解为 $ m \bmod a $ 对应的最小正整数余数
- inline 是内联函数，可以解决一些频繁调用的小函数大量消耗栈空间（栈内存）的问题，inline 的使用是有所限制的，inline 只适合函数体内代码简单的函数使用，不能包含复杂的结构控制语句例如 while、switch，并且内联函数本身不能是直接递归函数（即，自己内部还调用自己的函数）。