我正在尝试解决一个问题,其中 时间限制非常低 (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"
最佳答案
看一看:
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=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
关于math - 如何快速判断一个 "unknown"数是否可以被 3 整除?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47438429/