CF1873F Money Trees

Luca 站在一排共有 $n$ 棵树前。第 $i$ 棵树上有 $a_i$ 个果实，高度为 $h_i$。 他想选择一个连续子数组 $[h_l, h_{l+1}, \dots, h_r]$，使得对于每个 $i$（$l \leq i < r$），$h_i$ 能被 $h_{i+1}$ 整除。然后他会收集该子数组中所有树上的果实（即收集 $a_l + a_{l+1} + \dots + a_r$ 个果实）。但是，如果他收集的果实总数超过 $k$，他就会被抓住。 Luca 能选择的最长连续子数组长度是多少，且不会被抓住？ $^\dagger$ 若 $x$ 能被 $y$ 整除，则 $\frac{x}{y}$ 是整数。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 每个测试用例的第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^5$；$1 \leq k \leq 10^9$），分别表示树的数量和 Luca 能收集而不被抓住的最大果实数。 每个测试用例的第二行包含 $n$ 个用空格分隔的整数 $a_i$（$1 \leq a_i \leq 10^4$），表示第 $i$ 棵树上的果实数。 每个测试用例的第三行包含 $n$ 个用空格分隔的整数 $h_i$（$1 \leq h_i \leq 10^9$），表示第 $i$ 棵树的高度。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示满足条件的最长连续子数组的长度。如果不存在这样的子数组，输出 $0$。

在第一个测试用例中，Luca 可以选择 $l=1$ 且 $r=3$ 的子数组。 在第二个测试用例中，Luca 可以选择 $l=3$ 且 $r=4$ 的子数组。 在第三个测试用例中，Luca 可以选择 $l=2$ 且 $r=2$ 的子数组。 由 ChatGPT 4.1 翻译