読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #338 (Div. 2) D. Multipliers

問題文

codeforces.com

問題概要

ある整数 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。 前にも同じミスしたことあるので注意したい。