2883:互质问题

时间限制:5 S   /  内存限制:5120 KB
AC:72   /  Submit:141
问题描述

有一堆数字排成一排,涂涂希望删除其中尽可能少的数字后,就能满足任意相邻的两个数字都是互质的(最大公因数为1),问最少需要删除几个数字?

输入描述

多组案例。一个正整数n,表示案例的数量。(n<=20)

每组案例中,先是一个正整数m,表示数字的数量,(2<=m<=2000)

然后是m个正整数,每个数字都不大于100万。

输出描述

针对每组案例,输出一个整数,表示最少需要删除的数字数量。

每组案例输出完都要换行。

样例输入复制样例

3

5

1 2 3 4 5

5

2 4 6 8 10

6

2 6 3 9 2 6

样例输出

0

4

3

提示说明

第一组案例,任意两个相邻的数字都是互质的。

第二组案例,由于正偶数之间不互质,所以必须得删除其中4个,剩下任意一个。

第三组案例,在删除6、9、6这三个数字后能满足要求。

相关

19-20(2)第7次线上赛


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1