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

×

POWMIN - Editorial

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

asked 11 Oct '16, 12:36

mightysg's gravatar image

2★mightysg
41
accept rate: 0%

edited 02 Jan '17, 18:42

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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