行列積の定義より，です． の各要素が何を表してるかを考えると，求めたいものは 「の正の約数のうちで割り切れるものの個数」と言い換えることができます．
よってがで割り切れない場合の答えは明らかにです．以降はで割り切れるとします．
仮定より，はある整数を用いてと表すことができます． 実は求めたい答えは「の正の約数の個数」と一致することがわかります． なぜならば，の正の約数にをかけたものは明らかにの約数であり，かつの倍数でもあるからです．
あとはEratosthenesの篩などの高速に素因数分解ができるアルゴリズムを用いて各クエリに高速に答えることができればよいです． その場合の時間計算量は前計算で,各クエリにで答えることができるため， 全体の時間計算量はとしてとなり十分高速です．
一部の高速な言語での前計算なしでの各クエリも許容します．その場合の全体の時間計算量は上で用いたを用いて です．