Project Euler 38

题目

Pandigital multiples

Take the number 192 and multiply it by each of \(1, 2,\) and \(3\):

\(\begin{aligned} 192 \times 1 = 192\\ 192 \times 2 = 384\\ 192 \times 3 = 576\\ \end{aligned}\)

By concatenating each product we get the \(1\) to \(9\) pandigital, \(192384576\). We will call \(192384576\) the concatenated product of \(192\) and \((1,2,3)\)

The same can be achieved by starting with \(9\) and multiplying by \(1, 2, 3, 4,\) and \(5\), giving the pandigital, \(918273645\), which is the concatenated product of \(9\) and \((1,2,3,4,5)\).

What is the largest \(1\) to \(9\) pandigital \(9\)-digit number that can be formed as the concatenated product of an integer with \((1,2, \dots ,n)\) where \(n > 1\)?

解决方案

如果需要\(n>1\)，那么当任意一个数\(n\)，将\(n\)和\(2n\)拼接起来，长度会翻倍（很容易超过\(9\)），可以使用这个方法进行剪枝。

代码

b = "123456789"
ans = 0
for i in range(1, int(10**(len(b)/2))+4):
    t = ""
    for x in range(1, 10):
        t += str(i * x)
        if len(t) >= 9:
            break
    u = "".join((lambda x: (x.sort(), x)[1])(list(t)))
    if u == b:
        ans = max(ans, int(t))
print(ans)