codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2210C1.md (2771B)


      1 Source: https://codeforces.com/problemset/problem/2210/C1
      2 
      3 C1. A Simple GCD Problem (Easy Version)
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 This is the easy version of the problem. The difference between the versions is that in this version, $1 \leq n \leq 2 \cdot 10^{5}$ and $b_i = a_i$ for $1 \leq i \leq n$. Note that a solution for one version does not necessarily solve the other version. You can hack only if you solved all versions of this problem.
     22 
     23 You are given two arrays $a$ and $b$ of length $n$.
     24 
     25 For each index $i$ ($1 \le i \le n$) of array $a$, you can perform the following operation at most once:
     26 
     27 * choose an arbitrary integer $m$ ($\mathbf{m \neq a_i}$) such that $1 \leq m \le b_i$, and set $a_i := m$.
     28 
     29 Let the array after performing all the operations be $a'$. You can only perform operations in such a way that the following condition holds:
     30 
     31 * for all $1\leq l \lt r\leq n$, $\operatorname{gcd}(a_l,a_{l+1},\ldots,{a_r})=\operatorname{gcd}(a'_l,a'_{l+1},\ldots,a'_r).$
     32 
     33 Here, $\gcd(x, y)$ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $x$ and $y$.
     34 
     35 You have to determine the maximum number of operations that can be performed while ensuring that the condition remains satisfied.
     36 
     37 Input
     38 
     39 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     40 
     41 The first line of each test case contains an integer $n$ ($2 \leq n \leq 2\cdot 10^5$) — the length of $a$.
     42 
     43 The following line of each test case contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$).
     44 
     45 The next line of each test case contains $n$ space-separated integers $b_1, b_2, \ldots, b_n$ ($\color{red}{b_i = a_i}$).
     46 
     47 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.
     48 
     49 Output
     50 
     51 For each test case, output the maximum number of operations that can be done on a newline.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 4
     59 
     60 7
     61 
     62 1 2 3 4 5 6 7
     63 
     64 1 2 3 4 5 6 7
     65 
     66 3
     67 
     68 67 67 67
     69 
     70 67 67 67
     71 
     72 6
     73 
     74 8 10 10 12 12 14
     75 
     76 8 10 10 12 12 14
     77 
     78 8
     79 
     80 2 4 8 16 32 64 128 256
     81 
     82 2 4 8 16 32 64 128 256
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 6
     89 
     90 0
     91 
     92 2
     93 
     94 1
     95 ```
     96 
     97 Note
     98 
     99 For the first test case, the GCD of all subarrays is $1$. Hence, we can perform $6$ operations and change the array to $a' = [1, 1, 1, 1, 1, 1, 1]$. It can be shown that the maximum number of operations that can be performed in this case is $6$.
    100 
    101 For the second test case, note that all the values are equal, and reducing any value causes the GCD of subarrays to decrease. Hence, $0$ operations can be performed.
    102 
    103 For the third test case, it can be shown that at most $2$ operations can be performed.