math - 如何快速判断一个 "unknown"数是否可以被 3 整除？

Question

我正在尝试解决一个问题，其中 时间限制非常低 (1 秒)并且案例数量据说很高。

你需要判断一个数是否能被3整除，但问题是你没有得到直接数，得到一个数k，然后需要检查1到k(123. ..k) 可以被 3 整除。

示例输入:

4  // The number of cases
2
6
15
130000000

输出:

YES  // Because 12 is divisible by 3
YES  // Because 123456 is divisible by 3
YES  // Because 123456789101112131415 is divisible by 3
NO

我找到了一些关于快速检查可分性的主题，但我认为大部分时间是建立数字。在某些情况下，初始数字高达 130000000(所以最终数字是 1234...130000000)，我认为它会溢出任何数字数据类型。

那么，我在这里错过了什么？ 有没有办法在不连接数字的情况下知道某个东西是否可以被 3 整除？ 有什么想法吗？

PD:也有人贴了三角数公式，这也是一个正确的解决方案，然后删除了答案，它是:

if ((1 + num) * num / 2) % 3 == 0 ? "YES" : "NO"

Answer 1

每三个数字都可以被三整除。

每个能被 3 整除的数都有一个能被 3 整除的数位和。

每三个数字都有一个可被 3 整除的数字和。

在这些之间，每三个数字有一个数字和等于 1，然后是 2 mod 3。

看一看:

n    digit sum mod 3
0    0
1    1
2    2
3    0
4    1
5    2
6    0
...
10   1
11   2
12   0
...
19   1
20   2
21   0
...

假设我们按照您的描述构造了一串数字，我们刚刚添加的数字是可整除 mod 3 的数字。我们的数字，我们将得到一个与 1 mod 3 一致的组合数字和，所以我们对下一个的回答是“否”。下一个将添加一个数字总和与 2 mod 3 一致的数字，这会导致总数再次变为 0，所以这里的答案是"is"。最后，加上下一个必须能被 3 整除的数字，使数字和等于 0。

外卖？

如果 n 与 0 模 3 一致，则答案为"is"

如果 n 与 1 模 3 一致，则答案为“否”

如果 n 与 2 模 3 一致，则答案为"is"

特别是，您的 n=15 示例是错误的；得到的数字串代表一个应该能被 3 整除的数字，确实是(在足够大的计算器上试一试以验证)。

剩下的就是找到一个足够快并处理所有必需情况的实现。如果 n 保证低于约 20 亿，那么您可能使用类似的东西是安全的

return (n % 3) != 1;

如果 n 可以是一个任意大的数，不要害怕；您可以通过在线性时间内将数字相加来检查数字总和是否与 0 模 3 一致。如果不是，您可以通过编码加法从数字中添加 1，就像您在纸上手工完成一样，然后再次在线性时间内检查结果是否能被 3 整除。所以像:

if (digit_sum_mod_3(n) == 0) return true;
else if (digit_sum_mod_3(add_one(n)) == 0) return false;
else return true;

然后你会有类似的东西

digit_sum_mod_3(n[1...m])
    sum = 0
    for k = 1 to m do
        sum = sum + n[k]
        // keep sum from getting too big
        if sum >= 18 then
            sum = sum - 18
    return sum % 3

add_one(n[1...m])
    // work from right to left, assume big-endian
    for k = m to 1 do
        if n[k] < 9 then // don't need to carry
            n[k] = n[k] + 1
            break
        else then // need to carry
            n[k] = 0
    if n[1] = 0 then // carried all the way to the front
        n[1] = 1
        n[m+1] = 0
    return n