CodeIQ「『ディビジョン・サム』問題」の掲載期限が終了したということで、自分の提出コードを公開します。ほかの解答者のコードはTogetterにまとめらているので、ぜひご参考に。
"""
「ディビジョン・サム問題」(https://codeiq.jp/challenge/2903)の解答コード。
== 方針 ==
とある整数の約数の和は素因数分解を利用することができる。
たとえば整数mが次のように素因数分解できるとする: m = p^2 * q^3
このとき整数mの約数の和は (p^0 + p^1 + p^2) * (q^0 + q^1 + q^2 + q^3)
本問では巨大な整数n!^nを素因数分解を行う必要がある。
n!^n = 1^n * 2^n * ... * n^n であるから、1^n, 2^n, ... n^nを順番に因数分解することで、
最終的にn!^nの素因数分解の結果を求めることができる
"""
import collections, math
def prime_division(x):
"""
x > 0を満たす整数に対して素因数分解を行う。
戻り値はkeyが素数、valueが指数となるような辞書。
"""
ht = collections.defaultdict(int)
for factor in range(2, int(math.sqrt(x)) + 1):
if x == 1: break
while x % factor == 0:
ht[factor] += 1
x //= factor
if x != 1: ht[x] += 1
return ht
def geometric_sequence_sum(a, r, n):
"""
初項a,公比rの等比数列について第1項から第n項までの和を求める。
"""
return (a * (r ** n - 1)) // (r - 1)
def f(n):
"""
問題文中のF(n).
"""
# 1^n, 2^n, ... n^nについて素因数分解を行い、n!^nの素因数分解を行う。
factors = collections.defaultdict(int)
for x in range(2, n + 1):
for prime, exp in prime_division(x).items(): factors[prime] += exp * n
# (p^0 + p^1 + ... ) * (q^0 + q^1 + ...) * ... を求める。なお(p^0 + p^1 + ...)は等比数列である。
ans = 1
for prime, idx in factors.items():
ans = ans * geometric_sequence_sum(1, prime, idx+ 1) % (10 ** 6 + 3)
return ans
if __name__ == '__main__':
n = int(input())
print(f(n))
正直なところ解答ソースコードに書いた以上のことはないのですが、少しだけコメントしておきますね。
「『ディビジョン・サム』問題」はざっくりいうと「巨大数の約数の和を求める」という内容でした。整数の約数の和は素因数分解を利用して求めることができるということはよく知られています(大学受験などでは頻出ですね)。よって本問題は「与えられた巨大数をどれだけうまく素因数分解できるか」という点に集約できます。巨大数を愚直に生成して、それから素因数分解をする――という方法ではいうまでもなくうまくいきません。したがって愚直解ではなく、より洗練された方法に気が付くかという点が本問の肝だったように思います。