Znzryb's Blog
0%

模版1

Posted on

题目大意

题目描述
给定两个长度为 nn 的整数数组 aa 和 bb。
有 qq 次询问，每次询问给定一个区间 [l,r][l, r]，提取出子数组 a′=a[l…r]a' = a[l \dots r] 和 b′=b[l…r]b' = b[l \dots r]，设该子数组长度为 m=r−l+1m = r - l + 1。
对于每次询问中的子数组，可以执行以下操作任意次：

  1. 选取一个下标 ii（1≤i≤m1 \le i \le m）。

  2. 计算子数组后缀的最大公约数 gi=gcd⁡(a′∗i,a′∗i+1,…,am′)g_i = \gcd(a'*i, a'*{i+1}, \dots, a'_m)。

  3. 将 b′b' 中下标从 ii 到 mm 的所有元素减去 gig_i（即对于所有 i≤j≤mi \le j \le m，令 bj′←bj′−gib'_j \leftarrow b'_j - g_i）。

每次操作的代价为 1。要求计算出使 b′b' 中所有元素变为非正数（≤0\le 0）所需的最小总操作代价。

数据范围

  • 测试组数 TT：1≤T≤1051 \le T \le 10^5

  • 数组长度与询问次数 n,qn, q：1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5

  • 数组元素范围：1≤ai≤1091 \le a_i \le 10^9，0≤bi≤1090 \le b_i \le 10^9

  • 保证 ∑n≤106\sum n \le 10^6，∑q≤106\sum q \le 10^6

样例数据

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
10 10
6 12 18 40 50 60 105 120 135 150
10 20 30 40 50 60 70 80 90 100
5 8
1 3
7 10
6 6
4 7
1 6
2 10
2 4
4 4
5 6

输出

1
2
3
4
5
6
7
8
9
10
12
5
7
1
12
18
38
16
1
6

样例解释
以第 2 次询问 1 3 为例：
提取出的子数组为 a′=[6,12,18]a' = [6, 12, 18]，b′=[10,20,30]b' = [10, 20, 30]。
一种可能的最优操作序列如下（共需 5 次操作，代价为 5）：

  • 选取 i=1i = 1 操作 2 次：g1=gcd⁡(6,12,18)=6g_1 = \gcd(6, 12, 18) = 6，每次操作使 b1′,b2′,b3′b'_1, b'_2, b'_3 减去 6。操作后 b′b' 变为 [−2,8,18][-2, 8, 18]。

  • 选取 i=2i = 2 操作 2 次：g2=gcd⁡(12,18)=6g_2 = \gcd(12, 18) = 6，每次操作使 b2′,b3′b'_2, b'_3 减去 6。操作后 b′b' 变为 [−2,−4,6][-2, -4, 6]。

  • 选取 i=3i = 3 操作 1 次：g3=gcd⁡(18)=18g_3 = \gcd(18) = 18，每次操作使 b3′b'_3 减去 18。操作后 b′b' 变为 [−2,−4,−12][-2, -4, -12]。
    此时 b′b' 中所有元素均不大于 0，所需最小总代价为 2+2+1=52 + 2 + 1 = 5，与输出一致。

思路讲解

AC代码

心路历程（WA，TLE，MLE……）