class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int x: nums1){
            if(x % k != 0) continue;

            x /= k;

            for(int d = 1; d * d <= x; d ++ ){
                if(x % d > 0) continue;
                cnt.merge(d, 1, Integer::sum);
                if(d * d < x) cnt.merge(x / d, 1, Integer::sum);
            }
        }

        long ans = 0;
        for(int x: nums2){
            ans += cnt.getOrDefault(x, 0);
        }
        return ans;
    }
}