1117. 剩余定理

单点时限: 2.0 sec

内存限制: 256 MB

求正整数中满足:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … 的最小解。a[i] 是一些两两互质的正整数。

输入格式

输入数据的第一行为一个正整数 T,表示有 T 组测试数据。

每组测试数据的第一行为一个正整数 M,表示数组 a 和 b 中各有 M 个元素。0<M<=1000

接下来两行,每行各有 M 个正整数,分别为 a 和 b 中的元素。

输出格式

每组输出占一行,输出满足方程组的最小正解 X.

样例

Input
2
2
2 3
0 1
3
3 5 7
2 3 2
Output
4
23

352 人解决,418 人已尝试。

403 份提交通过,共有 817 份提交。

1.7 EMB 奖励。

创建: 17 年,9 月前.

修改: 7 年,4 月前.

最后提交: 2 月,1 周前.

来源: N/A

题目标签