PROBLEM LINKS:
Setter : Vatsal Gupta##
Tester : Shubham Grover##
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Number Theory
EXPLANATION:
Firstly, create a count array which stores the count of each number in the array
(since the maximum number in the array is no more than 10^6).
Since we know that for a number x the elements which satisfies the condition
(A%x==0) are actually the multiples of x and hence we need to travel the
multiples for every number, so clearly the idea is Sieve of Eratosthenes.
Important thing to note here is, since a number can appear any number of times,
we cannot travel from a number to all it’s multiples more than once (that will
result in TLE verdict). For that we maintained the count array and now for every
number we travel to it’s multiples once and subtract the value of the count of
that number from all it’s multiples (i.e. count[multiple]= max(count[multiple]-
count[x], 0) ).
Complexity: O(n*logn), where n<=10^6
SETTER’S SOLUTION:
Can be found here