问题
可以看得出,数字125874,和它的双倍数251748,总的来说有相同的数字,只不过是顺序不一样。
请找出最小的正整数x,使得2x、3x、4x、5x、6x,它们都含有相同的数字。
* 传送门
分析
如果题目不说是正整数,我立马就能给出答案,就是0。可惜是要找正整数……
直接暴力解题,按照它的描述把代码写出来就可以了。速度不快,但有用。
但本题还是有比较巧妙的设计。在解题论坛发现是有数学方法解的。
观察一个数的各个倍数,其实可以和另一种数学现象关联起来——无限循环小数。
举例,1/7 = 0.(142857)。循环小数的标记方法,其实是可以挪动位置的,例如 1/7 还可以记为 0.1(428571)、0.14(285714)等等。
这个现象有什么特别?可以观察:
- 1*142857 = 142857,相当于没移位的原始循环小数标记方法,又或者可以看作 1/7 = 0.(142857);
- 2*142857 = 285714,相当于移了2位的循环小数的标记方法,又或者可以看作 2/7 = 0.(285714);
- 3*142857 = 428571,相当于移了1位的循环小数的标记方法,又或者可以看作 3/7 = 0.(428571);
- 4*142857 = 571428,相当于移了4位的循环小数的标记方法,又或者可以看作 4/7 = 0.(571428);
- 5*142857 = 714285,相当于移了5位的循环小数的标记方法,又或者可以看作 5/7 = 0.(714285);
- 6*142857 = 857142,相当于移了3位的循环小数的标记方法,又或者可以看作 6/7 = 0.(857142);
- 7*142857 = 999999,这个就不用考虑了,因为 7/7 = 1,已经将循环性破坏了。
利用循环小数的倍数生成重复数位的数字是一种灵活的数学技巧。
显然本题答案就是142857。
P.S. 这个数字和题目的例子的数字也具有相同的数位,它们之间有什么关联呢?我却没什么头绪。
答案
// answer: brute force
const start = Date.now()
function to_digits(n) {
let digits_mask = 0
const digit_counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for (; n > 0; n = Math.floor(n / 10)) {
const digit = n % 10
digit_counts[digit]++
digits_mask |= (1 << digit)
}
return [digits_mask, digit_counts]
}
function with_same_digits(mask0, mask1, counts0, counts1) {
if ((mask0 ^ mask1) == 0) {
for (let d = 0; mask0 > 0; mask0 >>= 1, ++d)
if (counts0[d] != counts1[d])
return false
return true
}
return false
}
let result = 0
for (let n = 1; true; ++n) {
const [mask_1, counts_1] = to_digits(n)
let m = 2
for (; m <= 6; ++m) {
const [mask_m, counts_m] = to_digits(m*n)
if (!with_same_digits(mask_1, mask_m, counts_1, counts_m))
break
}
if (m > 6) {
result = n
break
}
}
alert(result + ', ' + (Date.now() - start) + 'ms')
打赏作者由 bruce 于 2018-04-12 14:15 更新