問題
解法
$M = \prod _ {t = 1} ^ l {p _ t} ^ {q _ t}$ と素因数分解されるとする．中国剰余定理より，各 $t = 1, \ldots, l$ に対して
$$\prod _ {i = 1} ^ K A _ i ^ t \equiv N \pmod {{p _ t} ^ {q _ t}}$$
を満たす列 $\{ A _ i ^ t \} _ {i = 1} ^ K \in (\Z/ {p _ t} ^ {q _ t} \Z) ^ K$ の個数 $x _ t$ を求めれば，答えは $\prod _ {t = 1} ^ l x _ t$ として求めることが出来る．
従って，$t$ 毎に独立に問題を解いてよいので，以降は次の部分問題を考える．
列 $\{ A _ i \} _ {i = 1} ^ K \in (\Z/ p ^ q \Z) ^ K$ であって，$\prod _ {i = 1} ^ K A _ i \equiv N \pmod {p ^ q}$ を満たすものの個数を求めよ．
整数 $x$ に対して，$v _ p(x)$ を $p$ が $x$ を割り切る回数と定義する．便宜上，$v _ p (0) = \infty$ と定義する．このとき，次の事実が成立する．
$X \equiv Y \pmod{ p ^ q }$ ならば，
- $Y \equiv 0 \pmod {p ^ q}$ のとき，$v _ p (X) \geq q$
- $Y \not\equiv 0 \pmod {p ^ q}$ のとき，$v _ p (X) = v _ p(Y)$
証明
$Y \equiv 0 \pmod {p ^ q}$ のとき
$X \equiv Y \equiv 0 \pmod {p ^ q}$ より，ある整数 $k$ が存在して $X = k \cdot p ^ q$ を満たすので $v _ p (X) \geq q$．
$Y \not \equiv 0 \pmod {p ^ q}$ のとき
$Y \not \equiv 0 \pmod {p ^ q}$ より $v _ p(Y) \lt q$ であり，$p$ と互いに素な整数 $Y'$ が存在して $Y = Y' \cdot p ^ {v _ p (Y)}$ と書ける．$X \equiv Y\pmod {p ^ q}$ より，ある整数 $k$ が存在して $X = Y + k \cdot p ^ q = p ^ {v _ p (Y)} ( Y' + k \cdot p ^ {q - v _ p (Y)})$ を満たす．
ここで，$v _ p(Y) \lt q$ より $k \cdot p ^ {q - v _ p (Y)}$ は $p$ の倍数であり，かつ $Y'$ は $p$ と互いに素であるから $Y' + k \cdot p ^ {q - v _ p (Y)}$ も $p$ と互いに素．従って，$X$ が $p$ で割り切れる回数はちょうど $v _ p (Y)$ である．
上記の事実に基づき，$N \equiv 0 \pmod {p ^ q}$ かどうかで場合分けをする．
$N \not\equiv 0 \pmod {p ^ q}$ の場合
$v _ p (\prod _ {i = 1} ^ K A _ i) = \sum _ {i = 1} ^ K v _ p (A _ i) = v _ p (N)$ を満たす必要がある．ここで，$v _ p (N) \lt q$ より $v _ p (A _ i) \lt q$ であることを注意しておく．
非負整数 $x \leq q$ を固定して $p$ と互いに素な整数 $a$ を動かしたときに，$a \cdot p ^ {x} \bmod p ^ q$ は何種類の値を取り得るかを考える．$x \leq q$ の下では，$a \cdot p ^ x \equiv b \cdot p ^ x \pmod {p ^ q}$ であることの必要十分条件は $a\equiv b \pmod {p ^ {q - x}}$ を満たすことであるから，結局 $\varphi (p ^ {q - x})$ 通りの値を取ることが分かる．
さて，各 $v _ p (A _ i)$ を固定した上で，$A _ 1, \ldots, A _ {K - 1}$ を自由に決めてしまうことにする．いま，$v _ p (A _ i) \lt q$ であるから，$A _ 1, \ldots, A _ {K - 1}$ の決め方は
$$\begin{aligned} \prod _ {i = 1} ^ {K - 1} \varphi (p ^ {q - v _ p (A _ i)}) &= \prod _ {i = 1} ^ {K - 1} p ^ {q - v _ p (A _ i) - 1} (p - 1) \\ &= \bigl( p ^ {q - 1} (p - 1) \bigr) ^ {K - 1} \cdot p ^ {-\sum _ {i = 1} ^ {K - 1} v _ p (A _ i)} \\ &= \bigl( p ^ {q - 1} (p - 1) \bigr) ^ {K - 1} \cdot p ^ {-(v _ p (N) - v _ p (A _ K))} \\ \end{aligned}$$
通りである．最後の行では $\sum _ {i = 1} ^ K v _ p (A _ i) = v _ p (N)$ を用いた．
ここで，$p$ と互いに素な整数 $a,b,c$ を用いて $\prod _ {i = 1} ^ {K - 1} A _ i = a \cdot p ^ {v _ p (N) - v _ p (A _ K)}$，$A _ K = b \cdot p ^ {v _ p (A _ K)}$，$N = c \cdot p ^ {v _ p (N)}$と表される．$\prod _ {i = 1} ^ K A _ i \equiv N \pmod {p ^ q} \iff ab\equiv c \pmod {p ^ {q - v _ p(N)}}$ であり，$a$ と $p$ は互いに素であるから，$b$ は $0 \leq b \lt p ^ {q - v _ p(N)}$ の範囲で一意存在する．先の議論から，$A _ K$ の値を考える上で $b$ は $\mathrm{mod}\; p ^ {q - v _ p(A _ K)}$ で同一視されるから，条件を満たす $A _ K$ は $p ^ {v _ p (N) - v _ p (A _ K)} $ 通りだけ存在する．
以上より，$v _ p (A _ i)$ を固定した場合に，条件を満たす $A$ は $\bigl( p ^ {q - 1} (p - 1) \bigr) ^ {K - 1}$ 個存在する．これは $v _ p (A _ i)$ に依らないので，結局全体では $H(v _ p (N), K) \cdot \bigl( p ^ {q - 1} (p - 1) \bigr) ^ {K - 1}$ 個存在する．ここで，$H$ は重複組合せを表し，$\displaystyle H(v _ p (N), K) = \binom{v _ p (N) + K - 1}{v _ p(N)}$ である．
$N \equiv 0 \pmod {p ^ q}$ の場合
このとき，$\prod _ {i = 1} ^ K \equiv N \pmod {p ^ q}$ であるための必要十分条件は，$\sum _ {i = 1} ^ K v _ p (A _ i) \geq q$ を満たすことである．$A _ i \equiv 0 \pmod {p ^ q}$ の場合を考慮する必要があるため，$\varphi (p ^ {q - v _ p(A _ i)})$ の計算に場合分けが発生する．そこで，$A _ i \not\equiv 0 \pmod {p ^ q}$ を満たす $i$ の個数 $j$ を固定して，$j$ の値毎に数え上げることを考える．
$j \lt K$ の場合
このとき，$\sum _ {i = 1} ^ K v _ p (A _ i) \geq q$ は必ず成立する．従って，$j$ を固定したときの求める列の個数は $\displaystyle \binom{K}{j} \cdot \bigl( p ^ {q - 1} (p - 1) \bigr) ^ j \cdot \Biggl(\sum _ {l = 0} ^ {q - 1} p ^ {-l}\Biggr) ^ j = \binom{K}{j} \cdot (p ^ q - 1) ^ j$ である．
これを $j = 0, \ldots, K - 1$ の範囲で和を取ると，以下のようになる．
$$\sum _ {j = 0} ^ {K - 1} \binom{K}{j} \cdot (p ^ q - 1) ^ j = (p ^ q) ^K - (p ^ q - 1) ^ K$$
$j = K$ の場合
このとき，$\sum _ {i = 1} ^ K v _ p (A _ i) \geq q$ は必ずしも成立しない．$\sum _ {i = 1} ^ K v _ p (A _ i) = k$ となる列 $A$ の個数は，多項式 $\displaystyle f(x) = \bigl( p ^ {q - 1} (p - 1) \bigr) ^ K \cdot \Biggl(\sum _ {l = 0} ^ {q - 1} p ^ {-l} x ^ l \Biggr) ^ K = (p - 1) ^ K \cdot \Biggl(\sum _ {l = 0} ^ {q - 1} p ^ {q - 1 - l} x ^ l \Biggr) ^ K$ の $x ^ k$ の係数として計算される．
求めたいのは $x ^ q, x ^ {q + 1}, \ldots $ の係数の和であるが，次数は最大でも $K (q - 1)$ にもなるため，実行時間制限に間に合わせるためには工夫する必要がある．$q$ は最大でも $\lfloor \log _ 2 M \rfloor$ 程度であるから，全ての係数の和から，$x ^ 0, \ldots, x ^ {q - 1}$ の係数の和を差し引くことを考える．全ての係数の和は $f(1)$ として計算され，即ち
$$(p - 1) ^ K \cdot \Biggl(\sum _ {l = 0} ^ {q - 1} p ^ {q - 1 - l} \Biggr) ^ K = (p - 1) ^ K \cdot \left(\dfrac{p ^ q - 1}{p - 1}\right) ^ K = (p ^ q - 1) ^ K$$
である．$f(x) \bmod x ^ q$ に関しては，例えば二分累乗法で $O(q ^ 2 \log K)$ や $O(q \log q \log K)$ などで計算することが出来る．
おわりに
難しいよ...
