0043 子串整除性
* * * *
拉格朗日计划
* * * *
子串整除性

1406357289是个0到9的全数字数(即0到9的每个数字在其中恰出现一次),此外它还具有如下的性质,称为子串整除性:

若$d_i$为它的第i个数字,则有

$d_2d_3d_4=206$能被2整除。

$d_3d_4d_5=063$能被3整除。

$d_4d_5d_6=635$能被5整除。

$d_5d_6d_7=357$能被7整除。

$d_6d_7d_8=572$能被11整除。

$d_7d_8d_9=728$能被13整除。

$d_8d_9d_{10}=289$能被17整除。

求所有满足该性质的0到9全数字数之和。

本题难度:



解答

可以筛出能分别被2,3,5,7,11,13,17整除的三位数再搜索。

不过鉴于数据量不算太大,直接生成0到9的全排列暴力搜索尽管速度慢,但写法比较简洁。

共有六个这样的数:1460357289、1406357289、1430952867、4160357289、4106357289、4130952867, 它们的和是$16695334890$。

import itertools
print sum(int("".join(s)) for s in itertools.permutations("0123456789") if all(int("".join(s[i+1:i+4]))%j==0 for i,j in enumerate([2,3,5,7,11,13,17])))