Project Euler #33 - 잘못 나눔

프로젝트 오일러 33번 - digit cancelling fractions
49 / 98 에서 '9'를 날려버리면 4 / 8 이 되는데, 이 경우 49 / 98 = 4 / 8 이 된다. 이런 경우를 모두 찾아서 모두 곱하고, 기약분수로 만들었을 때 분모는 무엇이 되는가?

30/50 = 3/5처럼 뻔한 경우를 빼면 이런 케이스가 딱 넷 있다고 문제에 써 있다. 49/98 하나는 알고 있으니 나머지 세 개를 찾으면 된다. 아마도 98 / 49 = 8 / 4 이런 건 아닐테니.. 분자가 분모보다 작은 경우만 생각하자. 숫자 세 개의 조합이니 암산도 가능할 듯..
a*10 + b 를 편의상 ab라고 써 보자.
ab / bc = a / c 가 되어야 한다. ab와 bc는 서로소이면 곤란하다. a=b이거나 a=c가 되어도 안 된다. a / c 를 생각하면 ab, bc가 둘 다 11로 나누어 떨어져야 하는데 22/22=2/2 처럼 "뻔한" 경우 밖에 안 나온다.
49/98 = 4/8,
16/64 = 1/4,

19/95 = 1/5
26/65 = 2/5

1/2 * 1/4 * 1/5 * 2/5 = 1/100
끝!

nu, de = 1, 1
for i in range(1,10):
    for j in {p for p in range(i+1,10)}:
        for k in {p for p in range(1,10) if p not in (i,j)}:
            if i * (k*10 + j) == j * (i*10 + k): nu *= i; de *= j

from sympy import factorint
rs = 1
for f in factorint(de):
    if f in factorint(nu): rs *= f**max(factorint(de)[f] - factorint(nu)[f],0)
    else: rs *= f**factorint(de)[f]

print rs

기약분수로 만들기 위해 소인수분해를 하는데, 딱 한 번만 할 거라 sympy에서 factorint를 가져왔다.