プロジェクトオイラー
http://projecteuler.net/index.php
Q168.
142857の7を前に持ってきて714285とすると、元の数が約数になるようなnの10 < n < 10100の総和の最後の5桁。
dを元の数の最後の桁の数字、mを桁数とすると、
10m-1d+(n-d)/10 = ((10m-1)d+n)/10
これが元の数のk倍になるから、
((10m-1)d+n)/10 = kn
n = d(10m-1)/(10k-1)
これが整数になることが必要条件。
簡単に計算できるが、せっかくなので大きな数の計算をしないように組んでみた。
import fractions# 10^e % d
def mod(e, d):
if e == 1:
return 10 % d
m = mod(e / 2, d)
if e % 2 == 1:
return m * m * 10 % d
else:
return m * m % d# return modulus when divide k(10^e - 1) / d by 10^f
def mod2(k, e, d, f):
n = 10 ** f
if e <= f:
return k * (10 ** e - 1) / d % n
q = k * n / d
r = k * n % d
for i in range(f, e):
r = r * 10
q = (q * 10 + r / d) % n
r %= d
if d == 1 and r == 0:
q = (q * 10 - 1) % n
return qdef f(m, d, k):
den = 10 * k - 1
div = fractions.gcd(d, den)
l = den / div
if mod(m, l) == 1 or l == 1:
n = mod2(d / div, m, l, 5)
if 10 * k < 11 * d and n % 10 == d:
return n
return 0N = 100
s = 0
for m in range(2, N + 1):
for d in range(1, 10):
for k in range(1, d + 1):
s += f(m, d, k)
print s % 10 ** 5
