素因数分解と最小公倍数について

本問では \(a_i\) を素因数分解された形で与えています。素因数分解自体の解説は高校数学の教科書や解説コンテンツ等に委ねますが、その性質に関するいくつかの前提知識を説明します。
まず、正整数 \(x\) の素因数分解における素数 \(p\) の指数を単に \(x\) の \(p\) の指数と呼ぶことにします。たとえば、\(20=2^2 \times 5\) の \(2\) の指数は \(2\) 、\(5\) の指数は \(1\) です。さらに、素因数分解の表記に現れない素数の指数は \(0\) として扱います。たとえば、\(20\) の \(3\) や \(998244353\) の指数は \(0\) です。
素因数分解に注目すると、正整数 \(x\) が正整数 \(y\) の倍数であることの必要十分条件は「任意の素数 \(p\) に対し、\(x\) の \(p\) の指数が \(y\) の \(p\) の指数以上である」と言えます。また、正整数 \(x_1,\ldots, x_k\) の最小公倍数は、各素数 \(p\) について、\(p\) の指数が「\(x_1,\ldots,x_k\) の\(p\) の指数の最大値」であるような正整数となります。

連想配列を用いた正整数の表現

本問は、\(i=1,\ldots,N\) に対して\(a_i\) を \(1\) に書き換えた場合の最小公倍数 \(L_1,\ldots,L_N\) を求めてその値の種類数を求めれば答えを得ることが出来ますが、このままだと実行時間制限超過となります。
まず、以下の問題点を考えます。

• \(a_i\) や \(L_i\) はとても大きな数になることがあり、64bit整数型で扱えないどころかメモリ制限に抵触し得る(たとえば、入出力例2の \(a_1\) はこれだけで4GB近くのメモリを使います)。

これに対し、素数をキー、その指数を値とした連想配列(無数に存在する指数が \(0\) である素数は無視してよい)を用いて \(a_i\) を管理し、\(L_i\) については連想配列のキーごとに \(\max\) を求める、とすればいくらか現実的なメモリサイズで正整数を扱うことが出来るようになります。

準線形時間への改善

さらなる改善のために、\(a_1,\ldots,a_N\) すべての最小公倍数 \(L\) と \(L_i\) について、\(L \neq L_i\) となる条件を考えます。最小公倍数を求める時にキーごとに \(\max\) を求めていることを考えると、「ある素数 \(p\) が存在して『 \(a_i\) の \(p\) の指数が \(L\) の \(p\) の指数に等しく、かつ \(a_j\) の \(p\) の指数が \(L\) の \(p\) の指数に等しいような \(j (\neq i)\) が存在しない』」というのが \(L \neq L_i\) となるための必要十分条件になります。また、\(L_i\) は \(p\) の指数が \(L\) のそれより小さくなった整数であり、(「 \(a_j\) の \(p\) の指数が \(L\) の \(p\) の指数に等しいような \(j (\neq i)\) が存在しない」ということを考えると) \(L_i \neq L_j(i \neq j)\) となります。
以上より、\(L \neq L_i\) となる \(i\) の個数 \(c\) が分かればそれに \(L=L_i\) の場合を加えることで答えが \(\min (c+1,N)\) と求められます。
\(L\) を表す連想配列の値として、 \(p\) の指数に加えてその指数を達成する \(i\) の個数を持たせれば、各 \(i\) について \(L \neq L_i\) であるかどうかを高速に判定することが出来、計算量は \(\mathrm O(\sum{m_i} \log \sum{m_i})\) となります(連想配列の操作の計算量を対数時間としています)。