310813: CF1891E. Brukhovich and Exams
Description
The boy Smilo is learning algorithms with a teacher named Brukhovich.
Over the course of the year, Brukhovich will administer $n$ exams. For each exam, its difficulty $a_i$ is known, which is a non-negative integer.
Smilo doesn't like when the greatest common divisor of the difficulties of two consecutive exams is equal to $1$. Therefore, he considers the sadness of the academic year to be the number of such pairs of exams. More formally, the sadness is the number of indices $i$ ($1 \leq i \leq n - 1$) such that $gcd(a_i, a_{i+1}) = 1$, where $gcd(x, y)$ is the greatest common divisor of integers $x$ and $y$.
Brukhovich wants to minimize the sadness of the year of Smilo. To do this, he can set the difficulty of any exam to $0$. However, Brukhovich doesn't want to make his students' lives too easy. Therefore, he will perform this action no more than $k$ times.
Help Smilo determine the minimum sadness that Brukhovich can achieve if he performs no more than $k$ operations.
As a reminder, the greatest common divisor (GCD) of two non-negative integers $x$ and $y$ is the maximum integer that is a divisor of both $x$ and $y$ and is denoted as $gcd(x, y)$. In particular, $gcd(x, 0) = gcd(0, x) = x$ for any non-negative integer $x$.
InputThe first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The descriptions of the test cases follow.
The first line of each test case contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 10^5$) — the total number of exams and the maximum number of exams that can be simplified, respectively.
The second line of each test case contains $n$ integers $a_1, a_2, a_3, \ldots, a_n$ — the elements of array $a$, which are the difficulties of the exams ($0 \leq a_i \leq 10^9$).
It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.
OutputFor each test case, output the minimum possible sadness that can be achieved by performing no more than $k$ operations.
ExampleInput9 5 2 1 3 5 7 9 5 2 3 5 7 9 11 8 2 17 15 10 1 1 5 14 8 5 3 1 1 1 1 1 5 5 1 1 1 1 1 19 7 1 1 2 3 4 5 5 6 6 7 8 9 10 1 1 1 2 3 1 15 6 2 1 1 1 1 2 1 1 2 1 1 1 2 1 2 5 2 1 1 1 1 2 5 2 1 0 1 0 1Output
1 0 2 2 0 5 5 2 1Note
In the first test case, a sadness of $1$ can be achieved. To this, you can simplify the second and fourth exams. After this, there will be only one pair of adjacent exams with a greatest common divisor (GCD) equal to one, which is the first and second exams.
In the second test case, a sadness of $0$ can be achieved by simplifying the second and fourth exams.
Output
**题目大意:**
有一个学生Smilo和他的老师Brukhovich,Brukhovich将在一年内举行n次考试,每次考试的难度$a_i$是一个非负整数。Smilo不喜欢当连续两次考试的难度最大公约数为1的情况。因此,他将以一年内这样的考试对数来衡量他的“悲伤度”。更正式地说,“悲伤度”是满足$gcd(a_i, a_{i+1}) = 1$的索引i的数量,其中$gcd(x, y)$是整数x和y的最大公约数。Brukhovich可以通过将任何考试的难度设置为0来减少Smilo的悲伤度,但他最多只能这样做k次。帮助Smilo确定Brukhovich在最多执行k次操作的情况下可以实现的最低悲伤度。
**输入数据格式:**
第一行包含一个整数$t$($1 \leq t \leq 10^4$)——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数$n$和$k$($1 \leq k \leq n \leq 10^5$)——考试的总数和可以简化的最大考试数。
第二行包含$n$个整数$a_1, a_2, a_3, \ldots, a_n$——数组$a$的元素,即考试的难度($0 \leq a_i \leq 10^9$)。
保证所有测试用例的$n$之和不超过$10^5$。
**输出数据格式:**
对于每个测试用例,输出通过执行不超过$k$次操作可以实现的最低可能的悲伤度。**E. Brukhovich and Exams** **题目大意:** 有一个学生Smilo和他的老师Brukhovich,Brukhovich将在一年内举行n次考试,每次考试的难度$a_i$是一个非负整数。Smilo不喜欢当连续两次考试的难度最大公约数为1的情况。因此,他将以一年内这样的考试对数来衡量他的“悲伤度”。更正式地说,“悲伤度”是满足$gcd(a_i, a_{i+1}) = 1$的索引i的数量,其中$gcd(x, y)$是整数x和y的最大公约数。Brukhovich可以通过将任何考试的难度设置为0来减少Smilo的悲伤度,但他最多只能这样做k次。帮助Smilo确定Brukhovich在最多执行k次操作的情况下可以实现的最低悲伤度。 **输入数据格式:** 第一行包含一个整数$t$($1 \leq t \leq 10^4$)——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数$n$和$k$($1 \leq k \leq n \leq 10^5$)——考试的总数和可以简化的最大考试数。 第二行包含$n$个整数$a_1, a_2, a_3, \ldots, a_n$——数组$a$的元素,即考试的难度($0 \leq a_i \leq 10^9$)。 保证所有测试用例的$n$之和不超过$10^5$。 **输出数据格式:** 对于每个测试用例,输出通过执行不超过$k$次操作可以实现的最低可能的悲伤度。