Project Euler Problem 032

http://projecteuler.net/index.php?section=problems&id=32
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2032

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

a * b = c で 9個の数字が1つずつ出てくる組み合わせを探す。

ちょっと手計算をすると以下のパターンの数字を探せば良いことがわかる。

  1桁 * 4桁 = 4桁
  2桁 * 3桁 = 4桁

そして、たとえば1桁の数が 9 のときは、4桁の数を全部調べなくても、積が 4 桁になるような 4桁の数字を調べれば良い。

まとめると以下のパターンを調べれば良いことがわかる。

  a(1桁) * b(4桁) = c(4桁)
    a = [ 1 .. 9 ]
    b = [ 1000 .. 10000 / a]
    c = [ 1000 .. 9999 ]

  a(2桁) * b(3桁) = c(4桁)
    a = [ 10 .. 99 ]
    b = [ 100 .. 10000 / a ]
    c = [ 1000 .. 9999 ]

上記を考慮して重複した数字 or 0 を含む時点で NG としながらGreedyに探した。

import math
import datetime


def is_pandigial(n, used):
    while n:
        m = n % 10
        if m in used:
            return False
        used.add(m)
        n /= 10
    return True


def euler031():
    result = set()
    
    cnt = 0
    for a in xrange(1, 100):
        used = set([0])
        
        if not is_pandigial(a, used):
            continue
        
        start = 1000 if a < 10 else 100
        stop  = int(math.ceil(10000.0 / a))
        
        for b in xrange(start, stop):
            c = a * b
            if c in result:
                continue
        
            used2 = used.copy()
            if not is_pandigial(b, used2):
                continue
        
            if not is_pandigial(c, used2):
                continue
        
            if len(used2) == 10:
                result.add(c)
                print '', (a, b, c)
            
    print sum(result)
    

begin = datetime.datetime.now()
euler031()
end = datetime.datetime.now()
print end - begin

答え: 45228
実行時間: 0.060493秒くらい