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)