题目描述以及思路
题目是需要求方程组的解,每个方程都是这样的模式:
$x\equiv m(mod\ a)$
可以将上面的式子转化为等式,因为对a取余操作本质上是去除了m当中的a的倍数,于是:
$x=ka+m$
对于两个方程:
$x=k_{1}a_{1}+m_{1},x=k_{2}a_{2}+m_{2}$
进行合并操作:
$k_{1}a_{1}+m_{1}=k_{2}a_{2}+m_{2}$
$k_{1}a_{1}-k_{2}a_{2}=m_{2}-m_{1}$
这个方程可以让我们联系到裴蜀定理,也就是:
对任意正整数a,b,一定存在整数x,y(至少有一者不为0),使得ax + by = gcd(a, b);
把$k_{1},k_{2}$视作x,y(可忽略正负号),如果$m_{2}-m_{1}$是gcd(a,b)的倍数,则公式有解。
于是我们的判定无解有解的条件就明了了。
求出解之后,设置$d=gcd(a_{1}, a_{2})$,可以把$k_{1}$的通解表示为:$k_{1}+K\frac{a_{2}}{d}$,对应的$k_{2}$的通解为$k_{2}+K\frac{a_{1}}{d}$,代入到方程当中可以发现回约掉后面的项。至于为什么需要除以d,除以d可以减少数的大小防止溢出风险。
因为使用扩展欧几里得公式求出来的是$k_{1}a_{1}+k_{2}a_{2}=gcd(a_1, a_2)$的解,所以要恢复成原式,需要在$k_{1}$的解上乘上$\frac{m_2-m_1}{gcd(a_1,a_2)}$
由公式$k_{1}+K\frac{a_{2}}{d}$,我们也可以知道其非负最小值为多少,因为这个公式其实和取余操作是等价的。设置$t = \frac{a_{2}}{d}$ 可以得到非负最小值为:
$k_{1}= ((k1\% t) + t) \% t$
代入求得的$k_{1}$,可以发现我们将两个公式合并成一个公式了:
$x=k_1a_1+m_1+K\frac{a_1a_2}{gcd(a_1,a_2)}$
这个公式当中,把K当作未知数,$k_1a_1+m_1$当作新公式的$m_1$,$\frac{a_1a_2}{gcd(a_1,a_2)}$当作新公式的$a_1$;
至此,我们完成了一个子任务,当有n个方程的时候,只需要进行n-1次上面的操作就好了;
最后只会得到一个公式,这时$x=k_1a_1+m_1$
需要求解最小的$k_{1}$,其实就是$((m1\%a_1)+a_1)\%a_1$
下面是代码:
#include<iostream>
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 res = exgcd(b, a % b, y, x);
y -= a / b * x;
return res;
}
int main()
{
int n;
cin >> n;
LL a1, m1;
cin >> a1 >> m1;
bool flag = true;
for(int i = 0; i < n - 1; i++)
{
LL a2, m2, k1, k2;
cin >> a2 >> m2;
LL d = exgcd(a1, a2, k1, k2);
if((m2 - m1) % d){
flag = false;
break;
}
k1 *= (m2 - m1) / d;
int t = a2 / d;
LL less = a1 / d * a2;
k1 = ((k1 % t) + t) % t;
m1 = k1 * a1 + m1;
a1 = less;
}
if(!flag) cout << -1 << endl;
else{
cout << ((m1 % a1) + a1) % a1 <<endl;
}
return 0;
}