読者です 読者をやめる 読者になる 読者になる

Problem 32

Project Euler

Problem 32

7254は面白い性質を持っている. 39 × 186 = 7254と書け, 
掛けられる数/掛ける数/積に1から9の数が1回ずつ出現する.
掛けられる数/掛ける数/積に1から9の数が1回ずつ出現するような積の総和を求めよ.
HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが
1回だけ数え上げよ.

a桁の整数とb桁の整数の積は a+b桁 or a+b-1桁 ですので、
全部で9個の数字からなる積算は

1桁 × 4桁 = 4桁
2桁 × 3桁 = 4桁

のいずれかしかありません。


つまり、この問題も力技で解けそうです。
というわけで、こんなプログラムを書いてみます。

fulfilled_numbers = set()
def add_if_fulfilled(a, b):
    global fulfilled_numbers
    c = a * b
    s = str(a) + str(b) + str(c)
    if len(s) == 9 and not '0' in s and len(set(s)) == 9:
        fulfilled_numbers.add(c)

for a in xrange(1, 10):
    for b in xrange(1000, 10000):
        add_if_fulfilled(a, b)
for a in xrange(10, 100):
    for b in xrange(100, 1000):
        add_if_fulfilled(a, b)

print sum(fulfilled_numbers)

計算時間 0.859 [sec] で解答を求めることができ、
答えは

45228

となります。