Project Euler 43

题目

Sub-string divisibility

The number, $1406357289$, is a $0$ to $9$ pandigital number because it is made up of each of the digits $0$ to $9$ in some order, but it also has a rather interesting sub-string divisibility property.

Let $d_1$ be the $1\text{st}$ digit, $d_2$ be the $2\text{nd}$ digit, and so on. In this way, we note the following:

$d2d_3d_4=406$ is divisible by $2$

$d_3d_4d_5=063$ is divisible by $3$

$d_4d_5d_6=635$ is divisible by $5$

$d_5d_6d_7=357$ is divisible by $7$

$d_6d_7d_8=572$ is divisible by $11$

$d_7d_8d_9=728$ is divisible by $13$

$d_8d_9d{10}=289$ is divisible by $17$

Find the sum of all $0$ to $9$ pandigital numbers with this property.

解决方案

可以直接用itertools库中的permutations产生所有置换，然后一个个直接进行判断。

比较一种优化的方法是自己手写深度优先搜索生成全排列，在恰当的地方及时剪枝，这将比上面的方法快不少。

代码

t = "0123456789"
ans = 0
for x in permutations(t):
    s = "".join(x)
    ok = 1
    if int(s[1:4]) % 2 != 0 or int(s[2:5]) % 3 != 0 or int(s[3:6]) % 5 != 0 or int(s[4:7]) % 7 != 0 or \
            int(s[5:8]) % 11 != 0 or int(s[6:9]) % 13 != 0 or int(s[7:10]) % 17 != 0:
        ok = 0
    if ok:
        ans += int(s)
print(ans)

N = 10
vis = [0 for i in range(N)]
val = [0 for i in range(N)]
m = [2, 3, 5, 7, 11, 13, 17]
ans = 0


def dfs(f: int):
    global ans
    if f == 10:
        ans += int("".join(str(x) for x in val))
        return

    for i in range(10):
        if vis[i]:
            continue
        if f == 0 and i == 0:
            continue
        if f >= 3:
            if (val[f - 2] * 100 + val[f - 1] * 10 + i) % m[f - 3] != 0:
                continue
        val[f] = i
        vis[i] = True
        dfs(f + 1)
        vis[i] = False


dfs(0)
print(ans)