×

# USF Editorial

Primary Tester: Amir Reza PoorAkhavan
Editorialist: Hussain Kara Fallah

Easy-Medium

# PREREQUISITES:

Sieve of Eratosthenes

# PROBLEM:

Given an array of N integers (all integers are up to $10^5$). Let's suppose we have taken a non-empty subset of this array. The magical value of this subset is (Number of distinct prime numbers that divides every number of the subset * the size of this subset). Find the subset with the maximum magical number and output this number.

# EXPLANATION:

First of all, Number of distinct prime numbers that divide every number of the subset is equivalent to the number of prime factors of GCD of this subset.

Let's try all possible GCDs. How's that possible?

If you don't know Sieve then stop reading and take a look at this link. After that, try to figure out the solution yourself.

What's the optimal subset for a certain GCD (let's say K) ?. Clearly, we can take a subset of all of its multiples in the array. Please note that the GCD of this subset would be K or one of its multiples, but that doesn't affect the answer (Why?). Because we will have the same subset when handling this (multiple of K) which is the real GCD and since it's a multiple of K, it has at least the same number of prime factors hence, the answer will be updated for sure. So we can safely assume the the GCD is equal to K with no problems.

How to loop over the multiples of a number K?

for(int i = K ; i < MX ; i += K){
tot += cnt[i]; //you can do anything
}


So our code looks like this:

for(int G = 2 ; G < MX ; G++){ //loop for every possible GCD
int subsetSize = 0;
for(int i = G ; i < MX ; i += G) // counting how many multiples there are
subsetSize += cnt[i];
}


The complexity of this loop is:

$$\sum_{i = 1}^{MaxValue} \frac{MaxValue}{i}$$

which is equal to:

$$MaxValue * \sum_{i = 1}^{MaxValue} \frac{1}{i}$$

The sum of the series:

$$\sum_{i = 1}^{MaxValue} \frac{1}{i} \approx log(MaxValue)$$

So total complexity is $MaxValue * log (MaxValue)$

There is also a part left for you, which is figuring the number of prime factors. This is easy, and can be done also while doing the Sieve approach (left for you), or you can check the codes.

# AUTHOR'S AND TESTER'S SOLUTIONS:

TESTER's solution

Editorialist's solution

This question is marked "community wiki".

108830
accept rate: 0%

19.7k350498541

This is not the sieve of Eratosthenes. In the sieve of Eratosthenes you only loop over multiple of primes. You use the sieve of Eratosthenes to find numbers of prime factors, and do it once before running the test cases.

(27 Nov '18, 04:36) 3★

 1 Another approach: Using the sieve of Eratosthenes precompute two arrays - numbers of prime factors and divisor lists. Create a zero-initialized array of useful numbers corresponding to each gcd value. For each element in the input array for each of its divisors add the contribution of the element to the useful number corresponding to the divisor. This contribution is the number of prime factors of the divisor. The answer is the maximum value in the resulting array. https://www.codechef.com/viewsolution/21706446 answered 27 Nov '18, 09:53 3★eugalt 282●7 accept rate: 4%
 1 Code is missing. answered 30 Nov '18, 23:55 3★prmondal 11●1 accept rate: 0%
 0 There is no explanation what cnt[i] is. Is it the number of prime factors? And where are the solution links? answered 25 Nov '18, 21:00 3★eugalt 282●7 accept rate: 4% 1 for(int i = G ; i < MX ; i += G) // counting how many multiples there are so it's clear that i is a multiple of G. and we said 2 lines before that we want to take a subset of all the multiples so it's the count of multiples in array. It's updated anyway (25 Nov '18, 23:05)
 0 How are we actually finding the gcd's of all subsets, I didn't get that part and also what is the proof for gcd's prime factors being answer and the prime factors of the subset? answered 26 Nov '18, 23:40 3★lmao_ 31●2 accept rate: 0% We are not finding gcds. We are fixing gcd, say X and calculating both number of distinct prime factors of X, as well as number of multiples of X present in array using sieve. We take maximum of product of this pair of values, for all valid X. (27 Nov '18, 00:08)
 0 Here are C++ and Python implementations. answered 27 Nov '18, 01:47 3★eugalt 282●7 accept rate: 4%
 toggle preview community wiki:
Preview

By Email:

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:

×3,706
×301
×56

question asked: 25 Nov '18, 01:20

question was seen: 1,573 times

last updated: 23 Dec '18, 16:30