Codeforces Round #338 (Div. 2) D. Multipliers
落とした。 $k$の部分でoverflowするのを見落としていた。
D. Multipliers
問題
整数$n$が、素因数分解された形で与えられる。 $n$の因数全ての積を${\rm mod} 1000000007$で求めよ。
解法
各素因数に関して、それが何回掛けられるかを求め、これを掛け合わせればよい。
$n = \Pi p_i^{k_i}$であるとき、 $k = \Pi(k_i+1)$として、 ${\rm ans} = \Pi p_i^{ {}_{k_i}C_2 \cdot \frac{k}{k_i+1}}$である。
$k$を直接使用するとoverflowないしtleするので、$l = {\rm lca}(k_i+1)$として、 ${\rm ans} = (\Pi p_i^{ {}_{k_i}C_2 \cdot \frac{l}{k_i+1}})^{\frac{k}{l}}$とすればよい。
実装
overflowに気を付けて多少の変形をする必要はあるが、同じ方針でc++でも実装できる。
#!/usr/bin/env python3
import math
lca = lambda a, b: a * b // math.gcd(a,b)
mod = 1000000007
m = int(input())
ps = map(int,input().split())
cnt = {}
for p in ps:
if p not in cnt:
cnt[p] = 0
cnt[p] += 1
lca_i = 1
k = 1
for i in cnt.values():
k *= i + 1
lca_i = lca(lca_i, i+1)
ans = 1
for p, i in cnt.items():
ans = ans * pow(p, i*(i+1)//2 * lca_i//(i+1), mod) % mod
ans = pow(ans, k//lca_i, mod)
print(ans)