\(p_1,p_2,p_3,\ldots\) を素数として \(M=p_1^{q_1} p_2^{q_2} p_3^{q_3}\ldots \) と表したとき、\((p_1,q_1),(p_2,q_2),(p_3,q_3),\ldots\) について

\(p\) を素数、\(q\) を \(1\) 以上の整数として、以下の条件を満たす長さ \(K\) の数列 \(a\) はいくつあるか？ \(\cdots (*)\)

• すべての \(i(1\leq i \leq K)\) について、\(0\leq a_i \leq p^q - 1\)
• \(\displaystyle \prod_{i=1}^{K}a_i \equiv N \pmod {p^q}\)

という問題を解きそれぞれの答えを掛け合わせることで、元の問題の答えを求めることができます。

\((*)\) を考えます。\((*)\) の答えを\( F(p,q,K,N)\) とします。

\(N_1\) と \(N_2\) で \(p\) の冪数が等しいとき、\(F(p,q,K,N_1)=F(p,q,K,N_2)\) が成り立ちます。(帰納法などで示せます。)
よって \(F(p,q,K,N)\) の値の種類数は \(p,q,K\) を固定すると \(O(\log_{ p}N)\) 程度になります。さらに、\(F(p,q,k,n)\) は \(F(p,q,k-1,n')\) の線形和で求まるため、行列累乗を用いれば \((*)\) を高速に求めることができます。

以上でこの問題を解くことができました。

補足

実装方針によっては途中で \(p-1\) や \(p\) で割る計算が発生しますが、これらが \(998244353\) の倍数だとゼロ除算になってしまうことに注意してください。