akinyan's favorite numbers

2 secs 1024 MB

$X$ の各素因数と $Y$ の各素因数についてそれぞれ積の累積和を取り、各 $i$ について $j$ を二分探索すればよいです.
計算量は $O(NlogNlogXY)$ です.
実装例(C++)