Hello, I need some help solving the current problem.
You have 4 arrays $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ all have the same size $$$N$$$, And It's guaranteed that for any index $$$1 <= i <= N$$$, $$$A_i mod B_i = 0$$$ and $$$C_i mod D_i$$$ = 0
You need to find the following : How many pairs (i,j) such that $$$(A_i / B_i) mod D_j = 0$$$ and $$$(C_j / D_j) mod B_i) = 0$$$
This isn't from any on-going contest, And you can assume the following
$$$N <= 10^5$$$
$$$A_i, B_i, C_i, D_i <= 10^5$$$
Bonus: Find for each number $$$x$$$, The number of pairs (i,j) that satisfies the requirement and $$$gcd(A_i / (B_i * D_j), C_j / (D_j*B_i)) = x$$$
Bump
Let's have some frequency tables for $$$A_i / B_i$$$, for $$$D_i$$$, for $$$C_i/D_i$$$ and for $$$B_i$$$. Let's call them $$$f1[], f2[], f3[], f4[]$$$ respectively.
Now let's compute the number of pairs of first kind. We iterate through each possible value $$$x\ (1 \le x \le 10^5)$$$, and for each $$$x$$$ we iterate through each of its multiples $$$y\ (y \le 10^5)$$$, and we add $$$f2[x]\cdot f1[y]$$$ to the answer.
Now, for the pairs of second kind, we can do something similar. We iterate though each possible value $$$x\ (1 \le x \le 10^5)$$$, and for each $$$x$$$ we iterate through each of its multiples $$$y\ (y \le 10^5)$$$, and we add $$$f4[x]\cdot f3[y]$$$ to the answer.
Now, what is the time complexity? For each $$$x$$$ we iterate through $$$\lfloor\frac{10^5}{x}\rfloor$$$ numbers, thus we are doing: $$$\sum_{i = 1}^{10^5} \lfloor\frac{10^5}{x}\rfloor \le 10^5 \cdot \log 10^5 $$$. Therefore this solution is efficient.