问题
可以看得出，数字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 更新
