SMALLSQ - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Akshay Venkataramani

Tester: Timothy

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Math, Sieve of Eratosthenes, Prime Factorization

EXPLANATION:

Let’s look at the solution using an example. Suppose the input is 60. The prime factorization is:

60 = 22 * 3 * 5

Looking at this might’ve given you a hint to the solution. The factors in the prime factorization of a square number have even powers. Hence, we just need to find the factors that have odd powers.

3 and 5 are the factors that have odd powers in the prime factorization of 60. Multiplying 60 by 15 (3*5) gives 900, which is a square number whose prime factorization is:

900 = 22 * 32 * 52

To find the prime factorization of a number, we slightly modify the Sieve of Eratosthenes to calculate and store the smallest prime factor for all numbers. This precalculation allows us to find the prime factorization extremely fast. The following routine is used to find the prime factorization:

map<ll,ll> factors;
while(n!=1)
{
    factors[smallestPrime[n]]++;
    n=n/smallestPrime[n];
}
return factors;

More info about this method can be found here. This method takes O(logn) to factorize a number.

AUTHOR’S AND TESTER’S SOLUTION:

Author’s solution can be found here.

Tester’s solution can be found here.