01 Matrix 2

行列積の定義より，$A^2_{x,y} = \sum^{N}_{k=1} A_{x,k} \times A_{k,y}$です． $A$の各要素が何を表してるかを考えると，求めたいものは 「$x$の正の約数のうち$y$で割り切れるものの個数」と言い換えることができます．

よって$x$が$y$で割り切れない場合の答えは明らかに$0$です．以降$x$は$y$で割り切れるとします．

仮定より，$x$はある整数$x'$を用いて$x = x' \times y$と表すことができます． 実は求めたい答えは「$x'$の正の約数の個数」と一致することがわかります． なぜならば，$x'$の正の約数に$y$をかけたものは明らかに$x$の約数であり，かつ$y$の倍数でもあるからです．

あとはEratosthenesの篩などの高速に素因数分解ができるアルゴリズムを用いて各クエリに高速に答えることができればよいです． その場合の時間計算量は前計算で$O(N \log{\log{N}})$,各クエリに$O(\log{(x_i\div y_i)})$で答えることができるため， 全体の時間計算量は$M= \max(x_i \div y_i)$として$O(N \log{ \log{N}} + Q \log{M})$となり十分高速です．

一部の高速な言語での前計算なしでの各クエリ$O(\sqrt{x_i \div y_i})$も許容します．その場合の全体の時間計算量は上で用いた$M$を用いて $O(Q \sqrt{M})$です．