You are not logged in. Please login at www.codechef.com to post your questions!

×

# POWMIN - Editorial

Easy-Medium

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

asked 11 Oct '16, 12:36

2★mightysg
41
accept rate: 0%

19.8k350498541

 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,710
×1,680
×631

question asked: 11 Oct '16, 12:36

question was seen: 508 times

last updated: 02 Jan '17, 18:42