POWMIN - Editorial

easy-medium
editorial
number-theory

#1

PROBLEM LINKS:

Practice

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