HDU 1573 - X问题 (中国剩余定理不互质情况)
思路
这题是中国剩余定理模r[i]的时候r[i]不互质的情况。
这时候就要用扩展欧几里得一个一个合并了。
就是说先算a[0]和a[1]的答案，再用上一个和a[2]算。以此类推。
简单些一下过程备忘。
$C \bmod a_1 = r_1$, $C \bmod a_2 = r_2$
$xa_1 + r_1 = y * a_2 + r_2$
$xa_1 + y^{‘} * a_2 = r2 - r1$
利用扩展欧几里得求出一个解x
可得$C = x*a_1 + r_1$
然后这个C就成为新的r1。这里搞不懂。$a_1$变成$LCM(a_1, a_2)$
就这样
代码
void Extend_GCD(LL a, LL b, LL &d, LL &x, LL &y)
{
if (!b) d = a, x = 1, y = 0;
else { Extend_GCD(b, a%b, d, y, x); y -= x * (a/b); }
}
LL a[MAXN], r[MAXN];
int main()
{
//ROP;
int T;
LL g;
cin >> T;
while (T--)
{
bool flag = false;
LL n, k, tmp;
cin >> n >> k;
for (int i = 0; i < k; i++) cin >> a[i];
for (int i = 0; i < k; i++) cin >> r[i];
LL a1 = a[0], r1 = r[0];
for (int i = 1; i < k; i++)
{
LL a2 = a[i], r2 = r[i], C = r2 - r1;
LL x, y;
Extend_GCD(a1, a2, g, x, y);
if (C % g)
{
flag = true;
break;
}
x = C / g * x;
tmp = a2 / g;
x = (x%tmp + tmp) % tmp;
r1 = a1 * x + r1;
a1 = a1 / g * a2;
}
if (flag || r1 > n) puts("0");
else
{
if (!r1) cout << (n-r1) / a1 << endl;
cout << (n-r1) / a1 + 1 << endl;
}
}
return 0;
}