Nが109まで行くのでO(N)を目指すと間に合わない。 そもそも七五三数は109以下に対して、3,5,7のみで構成される数値は、高々3**9 = 19683個しかないため、 この中から七五三数かつ、N以下のものを探す。
初め３進数として数え上げをしようとしたが、うまくいかず。itertools.productに変更。 今思うと、３進数ではゼロパディングをし忘れていた。
from itertools import product def solve(N): sum = 0 for k in range(1, 10): for i in product('357', repeat=k): if '3' in i and '5' in i and '7' in i: d = int("".join(list(i))) if d <= N: sum += 1 return sum if __name__ == "__main__": print(solve(int(input())))
N<=100のため、Nの累乗はそのままでは扱えない。 Nの累乗の素因数分解結果は、2, 3, 4, ... Nの素因数分解結果を統合したものに等しくなり、 この結合した素因数の部分集合はすべて、Nの累乗の約数であり、この中から七五数を見つける。
75個の正の整数の約数を持つとき、75 = 5 * 5 * 3 = 15 * 5 = 25 * 3であるため、 k, l, dを素因数とすると以下のいずれかを満たすことができる素因数の組み合わせを数えればよい。
k4 * l4 * d2
k4 * l14
k24 * l2
k74
from collections import Counter from itertools import combinations def prime_factors(n): c = Counter() while n > 1: for i in range(2, n + 1): if n % i == 0: c.update([i]) n //= i break return c def factrials(n): c = {} for i in range(2, n + 1): d = prime_factors(i) for k, v in d.items(): if k in c: c[k] += v else: c[k] = v return c def solve(N): facts = factrials(N) over2 = [k for k, v in facts.items() if v >= 2] over4 = [k for k, v in facts.items() if v >= 4] over14 = [k for k, v in facts.items() if v >= 14] over24 = [k for k, v in facts.items() if v >= 24] over74 = [k for k, v in facts.items() if v >= 74] sum = 0 # 4 - 4 - 2 sum += len([(d, d4) for d in over2 for d4 in combinations(over4, 2) if d not in d4]) # 4 - 14 sum += len([(d, d4) for d in over14 for d4 in over4 if d != d4]) # 2 - 24 sum += len([(d, d2) for d in over24 for d2 in over2 if d != d2]) # 74 sum += len(over74) return sum if __name__ == "__main__": print(solve(int(input())))
コンテストとしてはBeginnerだけれど初めての完答だった。
