题目翻译#

Ivy 在黑板上写下了从 $l$ 到 $r$ 的所有整数(包含 $l$ , $r$ )。

她执行以下操作：

在黑板上选择两个数字 $x$ 和 $y$ ，擦除它们，并在它们的位置写上数字 $3x$ 和 $\lfloor \frac{y}{3} \rfloor$ (此处 $\lfloor \bullet \rfloor$ 表示向下舍入到最接近的整数)。

Ivy 需要的最少操作数是多少才能使黑板上的所有数字相等 $0$ ？我们有一个证明，这总是可能的。

样例数量 $t$ ( $1 \leq t \leq 10^4$ )， $1 \leq l < r \leq 2 \cdot 10^5$ 。

解题思路#

不难发现，想要将其全部变为 0，首先需要 $x$ 总是等于 $0$ 。于是子问题变为：

如何最快获得一个 $0$ ？
在完成第一步后，在 $x = 0$ 的情况下，最快全部变为 0 需要 y /= 3 多少次？

由于数据范围为 $1 \leq l < r \leq 2 \cdot 10^5$ ，我们可以预处理每一个数循环除以 $3$ 变为 $0$ 的次数 $d_i$ ，再求出前缀和数组sum，便可以通过 sum[b] - sum[a - 1] 求出全部变为 0 的次数。

在获取第一个 $0$ 的过程中， $y$ 会被 y *= 3 $d_l$ 次，最终需要把它除回去，答案应当加上 $d_l$ 。

时间复杂度 $O(2e5)$ 。

完整代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
const int N = 2e5+5;
6
int d[N], sum[N];
7

8
int gd(int x){
9
    int cnt = 0;
10
    while(x){
11
        cnt++;
12
        x /= 3;
13
    }
14
    return cnt;
15
}
16

17
signed main(){
18
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
19

20
    for(int i = 1; i <= N - 1; i++){
21
        d[i] = gd(i);
22
        sum[i] = sum[i - 1] + d[i];
23
    }
24

25
    int cases;
26
    cin >> cases;
27
    for(int ii = 1; ii <= cases; ii++){
28
        sum[0] = 0;
29
        int l, r;
30
        cin >> l >> r;
31
        cout << sum[r] - sum[l - 1] + d[l] << endl;
32
    }
33
    return 0;
34
}