Many Positive Divisors

$A_1,A_2,\dots,A_N$ それぞれにおいて素因数分解したものの、素因数ごとの指数の和を求めることができれば、$\prod_{i=1}^N A_i$ の正の約数の個数を求めることができます。
しかし、試し割り法を用いた素因数分解では、整数 $M$ の素因数分解に $O(\sqrt{M\ })$ かかってしまい、間に合いません。(C++ なら間に合うかもしれませんが)
そこで、事前に $B_i=i$ の最小の素因数 であるような配列 $B$ を作ります。これはエラトステネスの篩を用いることで、$M$ 以下の整数に対応するものを $O(M\ log\ log\ M)$ で作成することができます。(典型 90 の 30 問目で用いるテクニックと似ています)
この配列 $B$ を用いて素因数分解を行うことで、整数 $M$ を $O(log\ M)$ で素因数分解することができます。
よって、整数列 $A$ の最大値を $M$ とすると、この問題を $O(N\ log\ M\ +\ M\ log\ log\ M)$ で解くことができました。