Zaee's blog

By Zaee, history, 2 years ago, In English

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$$$

Full text and comments »

  • Vote: I like it
  • -10
  • Vote: I do not like it