1 solutions

  • 1
    @ 2024-12-9 14:04:24

    考虑用三进制来书写这些数字(它与二进制类似,但我们使用了三位数字)。

    在运算中,我们将在数字 xx 的末尾加上一个 00 ,并去掉 yy 的最后一位数字。例如,如果 x=8x=8 和 y=11y=11 ,那么三元数就是 22322_{3} 和 1023102_{3} 。运算后, x=24x=24 和 y=3y=3 ,在三元数中实际上是 2203220_{3} 和 10310_{3} 。(这是因为乘以 33 等于乘以 10310_{3} ,同样,除以 33 等于除以 10310_{3} )。

    这意味着所有数字的总位数不会发生变化(因为我们增加了一位数,也去掉了一位数)。那么,怎样才能使所有数字都是 00 呢?

    上述规则有一个例外:当我们对 x=0x=0 进行运算时,我们会在数字 00 的末尾添加一个 00 ,但这个添加的数字并不算数(因为 3⋅0=03 \cdot 0 = 0 )。这意味着,如果我们再对 x=0x=0 进行运算,那么我们将总共损失一位数(因为 xx 没有增加一位数,而 yy 却损失了一位数)。

    这意味着解法如下:首先,我们让其中一个数字等于 00 。然后用这个 00 去掉所有其他数字的所有位数。为了尽可能减少运算次数,我们应该在最小的数字上进行第一步运算,因为它的位数最少。

    让 f(x)f(x) 表示数字 xx (实际上是 f(x)=⌊log⁡3(x)⌋+1f(x) = \lfloor \log_3 (x) \rfloor + 1 )中的三位数。那么第一步需要进行 f(l)f(l) 次运算(因为 ll 是范围 [l,r][l, r] 中最小的数字),第二步需要进行 f(l)+⋯+f(r)f(l) + \cdots + f(r) 次运算(因为我们需要删除所有数字,即从 ll 到 rr 的数字总数)。

    这意味着每个测试用例的答案都是 f(l)+f(l)+⋯+f(r)f(l) + f(l) + \cdots + f(r) 。为了快速求出这个和,我们可以计算 ff 的前缀和,这样答案就是 f(l)+psum(r)−psum(l−1)f(l) + \mathrm{psum}(r) - \mathrm{psum}(l-1) ,每个测试用例需要 O(1)\mathcal{O}(1) 的时间,加上 O(n)\mathcal{O}(n) 的预计算时间。

    • 1

    Information

    ID
    6
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    —
    Tags
    # Submissions
    4
    Accepted
    1
    Uploaded By