如何快速判断 "unknown" 数是否可以被 3 整除？
How to quickly tell if an "unknown" number is divisible by 3?
我正在尝试解决一个问题，其中时间限制非常短（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"
如果一个数的各位数字之和能被三整除，则该数能被三整除（参见 here）。因此，无需 "construct" 您的号码，您只需将各个号码的数字相加即可。因此，对于您的 15 情况，您不需要 "construct" 123456789101112131415，您只需要对 [1, 2, 3, 4, ... 14, 15] 中的所有数字求和即可。
你可以证明如果 n 或 n-2 可以被 3 整除，那么 n 的总和可以被 3 整除（例如，在你的例子中是 sum(1...8), sum(1.. 9), 求和(1..11), 等等).
任意三个连续数之和为 0 == a + a + 1 + a + 2 mod 3。
答案简化为 k%3 == 0，或 2k-1 % 3 == 0。后者相当于 k%3 == 2，省去了 k%3==1，然后进一步简化为 k%3 != 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，加上我们的数字，我们将得到与 1 mod 3 相等的组合数字和，因此我们对下一个的答案将是 "no"。下一位会加上一个数和等于2mod3的数，这就导致总数又变成0，所以这里的答案是"yes"。最后，加上下一个必须能被 3 整除的数字，使数字和等于 0。
外卖？
- 如果 n 等于 0 modulo 3，则答案是 "yes"
- 如果 n 等于 1 modulo 3，那么答案是 "no"
- 如果 n 等于 2 modulo 3，那么答案是 "yes"
特别是，您的 n=15 示例是错误的；得到的数字串代表一个应该被3整除的数字，确实是（用足够大的计算器来验证）。
剩下的就是找到一个足够快的实现并处理所有需要的情况。如果 n 保证在 20 亿以下，那么你可能对
这样的东西是安全的
return (n % 3) != 1;
如果n可以是任意大的数，不要害怕；您可以通过在线性时间内将数字相加来检查数字和是否与 0 modulo 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
如果一个数的各个小数位的总和可以被三整除，那么这个数就可以被三整除，这是一个众所周知的数学技巧。
示例：
2271
2+2+7+1 = 12
12 is divisible by 3, therefore so is 2271
另外，任意三个连续整数的和必须能被三整除。这是因为：
((n)+(n+1)+(n+2))/3 = (3n+3)/3 = n+1 = integer
因此：
如果 k mod 3 == 0，则 1 到 k 的串联可被三整除。
如果k mod 3 == 1，则1到k的串联不能被三整除。
如果k mod 3 == 2，那就有点棘手了。在这种情况下，如果 k 和 k 之前的数字之和（计算结果为 (k)+(k-1)，即 [=24]，则 1 到 k 的串联可被三整除=]) 可以被三整除。
因此，最终条件为：
(k mod 3 == 0) || ((k mod 3 == 2) && (2k-1 mod 3 == 0))
不过，这还可以进一步简化。
事实证明，当 2k-1 mod 3 等于 0 时，k mod 3 只能等于 2，反之亦然。
请参阅下面的简单图表，其中显示了此行为的循环模式。
因此，公式可以进一步简化为：
(k mod 3 == 0) || (k mod 3 == 2)
或者，更简单地说：
(k mod 3 != 1)
我知道回答者已经提供了这个答案，所以我不希望这是公认的答案，只是给出更详尽的数学解释。
这比听起来简单，因为问题只需要检查非常特定格式的数字：12345789101112131415…k。您可以使用高斯方法快速获得数字 1 到 k 的总和，然后使用通常的方法检查该总和是否可以被三整除。代码是：
'NO' if (k*(k+1)/2)%3 else 'YES'
如果您查看随着 k 增加而出现的模式（NO，YES，YES，NO，YES，YES，...），您甚至不需要乘法或除法。简而言之，您只需要：
'YES' if (k-1)%3 else 'NO'
这里是 Python 代码，它从文件中读取整数，如果不会花费太长时间，还会以困难的方式检查答案，以便您可以看到它是正确的。 （Python数字可以无限长，不用担心溢出）：
#!/usr/bin/python3
# Read integers from stdin, convert each int to a triangular number
# and output YES (or NO) if it is divisible by 3.
def sumgauss(x):
'''Return the sum from 1 to x using Gauss's shortcut'''
return (x*(x+1)/2)
def triangle(n):
'''Given an integer n, return a string with all the integers
from 1 to n concatenated. E.g., 15 -> 123456789101112131415'''
result=""
for t in range(1, k+1):
result+=str(t)
return result
import sys
for k in sys.stdin.readlines():
k=int(k)
print ( 'YES' if (k-1)%3 else 'NO', end='')
# If it wouldn't take too long, double check by trying it the hard way
if k<100000:
kstr=triangle(k)
print("\t// %s modulo 3 is %d" % (kstr, int(kstr)%3))
else:
print('\t// 123456789101112131415...%d%d%d modulo 3 is %d' %
tuple([k-2, k-1, k, sumgauss(k)%3]))
说起高斯求和的捷径，这道题很像作业。 （高斯在学生时代发明了它，当时一位老师试图通过让他们将 1 到 100 的数字相加来让 class 从他的头发上脱落一段时间。）如果这确实是一个 class作业，请确保老师知道把 A 给我和 Whosebug。谢谢！
示例输出：
$ cat data
2
6
15
130000000
130000001
$ ./k3.py < data
YES // 12 modulo 3 is 0
YES // 123456 modulo 3 is 0
YES // 123456789101112131415 modulo 3 is 0
NO // 123456789101112131415...129999998129999999130000000 modulo 3 is 1
YES // 123456789101112131415...129999999130000000130000001 modulo 3 is 0
前32个三角数：
$ seq 32 | ./k3.py
NO // 1 modulo 3 is 1
YES // 12 modulo 3 is 0
YES // 123 modulo 3 is 0
NO // 1234 modulo 3 is 1
YES // 12345 modulo 3 is 0
YES // 123456 modulo 3 is 0
NO // 1234567 modulo 3 is 1
YES // 12345678 modulo 3 is 0
YES // 123456789 modulo 3 is 0
NO // 12345678910 modulo 3 is 1
YES // 1234567891011 modulo 3 is 0
YES // 123456789101112 modulo 3 is 0
NO // 12345678910111213 modulo 3 is 1
YES // 1234567891011121314 modulo 3 is 0
YES // 123456789101112131415 modulo 3 is 0
NO // 12345678910111213141516 modulo 3 is 1
YES // 1234567891011121314151617 modulo 3 is 0
YES // 123456789101112131415161718 modulo 3 is 0
NO // 12345678910111213141516171819 modulo 3 is 1
YES // 1234567891011121314151617181920 modulo 3 is 0
YES // 123456789101112131415161718192021 modulo 3 is 0
NO // 12345678910111213141516171819202122 modulo 3 is 1
YES // 1234567891011121314151617181920212223 modulo 3 is 0
YES // 123456789101112131415161718192021222324 modulo 3 is 0
NO // 12345678910111213141516171819202122232425 modulo 3 is 1
YES // 1234567891011121314151617181920212223242526 modulo 3 is 0
YES // 123456789101112131415161718192021222324252627 modulo 3 is 0
NO // 12345678910111213141516171819202122232425262728 modulo 3 is 1
YES // 1234567891011121314151617181920212223242526272829 modulo 3 is 0
YES // 123456789101112131415161718192021222324252627282930 modulo 3 is 0
NO // 12345678910111213141516171819202122232425262728293031 modulo 3 is 1
YES // 1234567891011121314151617181920212223242526272829303132 modulo 3 is 0
其实答案很简单，如果数字之和能被3整除那么这个数也能被3整除
字符串 ans=(((1 + num) * num) / 2) % 3 == 0 ? “是”：“否”；
根据题目sum of digit可以认为是1到n的数字之和，sum=(n*(n+1))/2
*确保将整个事情除以 2
另一种方法：
字符串 ans=n % 3 !=1 ? “是”：“否”；
我正在尝试解决一个问题，其中时间限制非常短（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"
如果一个数的各位数字之和能被三整除，则该数能被三整除（参见 here）。因此，无需 "construct" 您的号码，您只需将各个号码的数字相加即可。因此，对于您的 15 情况，您不需要 "construct" 123456789101112131415，您只需要对 [1, 2, 3, 4, ... 14, 15] 中的所有数字求和即可。
你可以证明如果 n 或 n-2 可以被 3 整除，那么 n 的总和可以被 3 整除（例如，在你的例子中是 sum(1...8), sum(1.. 9), 求和(1..11), 等等).
任意三个连续数之和为 0 == a + a + 1 + a + 2 mod 3。
答案简化为 k%3 == 0，或 2k-1 % 3 == 0。后者相当于 k%3 == 2，省去了 k%3==1，然后进一步简化为 k%3 != 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，加上我们的数字，我们将得到与 1 mod 3 相等的组合数字和，因此我们对下一个的答案将是 "no"。下一位会加上一个数和等于2mod3的数，这就导致总数又变成0，所以这里的答案是"yes"。最后，加上下一个必须能被 3 整除的数字，使数字和等于 0。
外卖？
- 如果 n 等于 0 modulo 3，则答案是 "yes"
- 如果 n 等于 1 modulo 3，那么答案是 "no"
- 如果 n 等于 2 modulo 3，那么答案是 "yes"
特别是，您的 n=15 示例是错误的；得到的数字串代表一个应该被3整除的数字，确实是（用足够大的计算器来验证）。
剩下的就是找到一个足够快的实现并处理所有需要的情况。如果 n 保证在 20 亿以下，那么你可能对
这样的东西是安全的return (n % 3) != 1;
如果n可以是任意大的数，不要害怕；您可以通过在线性时间内将数字相加来检查数字和是否与 0 modulo 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
如果一个数的各个小数位的总和可以被三整除，那么这个数就可以被三整除，这是一个众所周知的数学技巧。
示例：
2271
2+2+7+1 = 12
12 is divisible by 3, therefore so is 2271
另外，任意三个连续整数的和必须能被三整除。这是因为：
((n)+(n+1)+(n+2))/3 = (3n+3)/3 = n+1 = integer
因此：
如果 k mod 3 == 0，则 1 到 k 的串联可被三整除。
如果k mod 3 == 1，则1到k的串联不能被三整除。
如果k mod 3 == 2，那就有点棘手了。在这种情况下，如果 k 和 k 之前的数字之和（计算结果为 (k)+(k-1)，即 [=24]，则 1 到 k 的串联可被三整除=]) 可以被三整除。
因此，最终条件为：
(k mod 3 == 0) || ((k mod 3 == 2) && (2k-1 mod 3 == 0))
不过，这还可以进一步简化。
事实证明，当 2k-1 mod 3 等于 0 时，k mod 3 只能等于 2，反之亦然。
请参阅下面的简单图表，其中显示了此行为的循环模式。
因此，公式可以进一步简化为：
(k mod 3 == 0) || (k mod 3 == 2)
或者，更简单地说：
(k mod 3 != 1)
我知道回答者已经提供了这个答案，所以我不希望这是公认的答案，只是给出更详尽的数学解释。
这比听起来简单，因为问题只需要检查非常特定格式的数字：12345789101112131415…k。您可以使用高斯方法快速获得数字 1 到 k 的总和，然后使用通常的方法检查该总和是否可以被三整除。代码是：
'NO' if (k*(k+1)/2)%3 else 'YES'
如果您查看随着 k 增加而出现的模式（NO，YES，YES，NO，YES，YES，...），您甚至不需要乘法或除法。简而言之，您只需要：
'YES' if (k-1)%3 else 'NO'
这里是 Python 代码，它从文件中读取整数，如果不会花费太长时间，还会以困难的方式检查答案，以便您可以看到它是正确的。 （Python数字可以无限长，不用担心溢出）：
#!/usr/bin/python3
# Read integers from stdin, convert each int to a triangular number
# and output YES (or NO) if it is divisible by 3.
def sumgauss(x):
'''Return the sum from 1 to x using Gauss's shortcut'''
return (x*(x+1)/2)
def triangle(n):
'''Given an integer n, return a string with all the integers
from 1 to n concatenated. E.g., 15 -> 123456789101112131415'''
result=""
for t in range(1, k+1):
result+=str(t)
return result
import sys
for k in sys.stdin.readlines():
k=int(k)
print ( 'YES' if (k-1)%3 else 'NO', end='')
# If it wouldn't take too long, double check by trying it the hard way
if k<100000:
kstr=triangle(k)
print("\t// %s modulo 3 is %d" % (kstr, int(kstr)%3))
else:
print('\t// 123456789101112131415...%d%d%d modulo 3 is %d' %
tuple([k-2, k-1, k, sumgauss(k)%3]))
说起高斯求和的捷径，这道题很像作业。 （高斯在学生时代发明了它，当时一位老师试图通过让他们将 1 到 100 的数字相加来让 class 从他的头发上脱落一段时间。）如果这确实是一个 class作业，请确保老师知道把 A 给我和 Whosebug。谢谢！
示例输出：
$ cat data
2
6
15
130000000
130000001
$ ./k3.py < data
YES // 12 modulo 3 is 0
YES // 123456 modulo 3 is 0
YES // 123456789101112131415 modulo 3 is 0
NO // 123456789101112131415...129999998129999999130000000 modulo 3 is 1
YES // 123456789101112131415...129999999130000000130000001 modulo 3 is 0
前32个三角数：
$ seq 32 | ./k3.py
NO // 1 modulo 3 is 1
YES // 12 modulo 3 is 0
YES // 123 modulo 3 is 0
NO // 1234 modulo 3 is 1
YES // 12345 modulo 3 is 0
YES // 123456 modulo 3 is 0
NO // 1234567 modulo 3 is 1
YES // 12345678 modulo 3 is 0
YES // 123456789 modulo 3 is 0
NO // 12345678910 modulo 3 is 1
YES // 1234567891011 modulo 3 is 0
YES // 123456789101112 modulo 3 is 0
NO // 12345678910111213 modulo 3 is 1
YES // 1234567891011121314 modulo 3 is 0
YES // 123456789101112131415 modulo 3 is 0
NO // 12345678910111213141516 modulo 3 is 1
YES // 1234567891011121314151617 modulo 3 is 0
YES // 123456789101112131415161718 modulo 3 is 0
NO // 12345678910111213141516171819 modulo 3 is 1
YES // 1234567891011121314151617181920 modulo 3 is 0
YES // 123456789101112131415161718192021 modulo 3 is 0
NO // 12345678910111213141516171819202122 modulo 3 is 1
YES // 1234567891011121314151617181920212223 modulo 3 is 0
YES // 123456789101112131415161718192021222324 modulo 3 is 0
NO // 12345678910111213141516171819202122232425 modulo 3 is 1
YES // 1234567891011121314151617181920212223242526 modulo 3 is 0
YES // 123456789101112131415161718192021222324252627 modulo 3 is 0
NO // 12345678910111213141516171819202122232425262728 modulo 3 is 1
YES // 1234567891011121314151617181920212223242526272829 modulo 3 is 0
YES // 123456789101112131415161718192021222324252627282930 modulo 3 is 0
NO // 12345678910111213141516171819202122232425262728293031 modulo 3 is 1
YES // 1234567891011121314151617181920212223242526272829303132 modulo 3 is 0
其实答案很简单，如果数字之和能被3整除那么这个数也能被3整除
字符串 ans=(((1 + num) * num) / 2) % 3 == 0 ? “是”：“否”；
根据题目sum of digit可以认为是1到n的数字之和，sum=(n*(n+1))/2 *确保将整个事情除以 2
另一种方法： 字符串 ans=n % 3 !=1 ? “是”：“否”；