首页 > 试题广场 >

黑妹的游戏IV

[编程题]黑妹的游戏IV
黑妹又来玩游戏了，这次她面对的是两个长度为n的正整数序列A和B，并且她要维护两个二元序对集合S1和S2，初始时这两个集合是空的，每一次她可以进行一次操作，
选择满足以下条件的两个序对(i, j)和(p, q)，
1.(i, j)不在S1中并且(p, q)不在S2中。
2. Ai < Bj, Aq > Bp。
3. Ai 和 Bj 不互质, Aq 和 Bp 不互质。
4. gcd(Ai, Bj) 和 gcd(Aq, Bp) 不互质。
然后把(i, j)加入集合S1，(p, q)加入集合S2。
但是她又很快玩腻了这个游戏，她现在想知道她最多能进行多少次操作。

输入描述:
第一行一个整数T表示测试数据组数。(1 ≤ T ≤ 10)

对于每组数据：

第一行一个整数n表示序列的长度。(1 ≤ n ≤ 400)

接下来一行n个整数表示序列A的每个元素。(1 ≤ Ai ≤ 109)

接下来一行n个整数表示序列B的每个元素。(1 ≤ Bi ≤ 109)


输出描述:
对于每组数据输出一行表示答案。
示例1

输入

2
4
5 2 3 4
5 2 3 4
4
2 5 6 14
3 4 7 10

输出

1
3
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

网络流
难度：
0条回答 7浏览

热门推荐

通过挑战的用户

查看代码

相关试题

黑妹的游戏IV

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号