Codeforces Round #338 (Div. 2) D. Multipliers
問題文
問題概要
ある整数 n の素因数のリスト p1, p2, ... , pm が与えられるので、 n のすべての約数を掛けあわせた値を求めよ。
解法
n = p1e1 p2e2 p3e3... と表せたとする。
pmk... の形の約数は (e1+1)(e2+1)(e3+1).../(em+1) 個あるので、 答えには pmk が (e1+1)(e2+1)(e3+1).../(em+1) 個含まれる。
よって、pow(pmk, (e1+1)(e2+1)(e3+1).../(em+1)) をすべての m, k で計算し掛けあわせれば答えが出る。
指数の計算は累積積や segtree を使えばいい。 指数を mod 109+6 しても値は変わらないので、mod 109+6 で積を計算するといい。
値が変わらないことはフェルマーの小定理によって保証できる。
今回の場合、偶数は逆元を持たないため逆元を使うことが出来ない。
Codeforces Round #338 (Div. 2) D. Multipliers
指数を mod 109+7 してしまい Hacked。
前にも同じミスしたことあるので注意したい。