Project Euler 157

プロジェクトオイラー
http://projecteuler.net/index.php

Q157.
1/a + 1/b = p/10nの1 ≤ n ≤ 9での解の個数

比較的平易な問題だが、1 ≤ n ≤ 9というのがよくわからなかった。これは、例えば、

1/2 + 1/5 = 7/10
1/2 + 1/5 = 70/100

これらは別の解ということである。ここがなかなかわからなかった。



from itertools import product
from math import sqrt
import fractions

def make_primes(limit):
for n in xrange(3, limit + 1, 2):
if is_prime(n):
primes.append(n)
return primes

def is_prime(n):
for p in primes:
if p * p > n:
return True
elif n % p == 0:
return False
return True

def num_divisors(n, p0 = 1):
if n == 1:
return 1
for p in primes:
if p * p > n:
return 2
if p <= p0:
continue
if n % p == 0:
n /= p
rep = 1
while n % p == 0:
n /= p
rep += 1
return (rep + 1) * num_divisors(n, p)
return 2

def e(n, p):
counter = 0
while n % p == 0:
counter += 1
n /= p
return counter

def gen_exp(n):
for q, r in product(range(n + 1), repeat = 2):
k = 2 ** q
l = 5 ** r
yield k, l, n - q + 1, n - r + 1
if q > 0 and r > 0:
yield 1, k * l, n - q + 1, n - r + 1

def num_solutions(n):
counter = 0
for k, l, s, t in gen_exp(n):
kl = k + l
ds = e(kl, 2)
dt = e(kl, 5)
s += ds
t += dt
kl /= 2 ** ds * 5 ** dt

counter += num_divisors(kl) * s * t
print counter
return counter

N = 9
primes = [ 2 ]
make_primes(int(sqrt(2 ** N + 5 ** N + 0.5)))

print sum(map(num_solutions, range(1, N + 1)))