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

よってxxyyで割り切れない場合の答えは明らかに00です.以降xxyyで割り切れるとします.

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

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

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