1 solutions
-
1
考虑用三进制来书写这些数字(它与二进制类似,但我们使用了三位数字)。
在运算中,我们将在数字 的末尾加上一个 ,并去掉 的最后一位数字。例如,如果 和 ,那么三元数就是 和 。运算后, 和 ,在三元数中实际上是 和 。(这是因为乘以 等于乘以 ,同样,除以 等于除以 )。
这意味着所有数字的总位数不会发生变化(因为我们增加了一位数,也去掉了一位数)。那么,怎样才能使所有数字都是 呢?
上述规则有一个例外:当我们对 进行运算时,我们会在数字 的末尾添加一个 ,但这个添加的数字并不算数(因为 )。这意味着,如果我们再对 进行运算,那么我们将总共损失一位数(因为 没有增加一位数,而 却损失了一位数)。
这意味着解法如下:首先,我们让其中一个数字等于 。然后用这个 去掉所有其他数字的所有位数。为了尽可能减少运算次数,我们应该在最小的数字上进行第一步运算,因为它的位数最少。
让 表示数字 (实际上是 )中的三位数。那么第一步需要进行 次运算(因为 是范围 中最小的数字),第二步需要进行 次运算(因为我们需要删除所有数字,即从 到 的数字总数)。
这意味着每个测试用例的答案都是 。为了快速求出这个和,我们可以计算 的前缀和,这样答案就是 ,每个测试用例需要 的时间,加上 的预计算时间。
- 1
Information
- ID
- 6
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- —
- Tags
- # Submissions
- 4
- Accepted
- 1
- Uploaded By