Number Theory Problem

Revision en1, by Zaee, 2020-12-06 05:10:48

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Zaee 2020-12-06 05:10:48 623 Initial revision (published)