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

×

SMALLSQ - Editorial

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.

This question is marked "community wiki".

asked 21 Jan '18, 17:32

accelmage's gravatar image

4★accelmage
52
accept rate: 0%

edited 05 Feb '18, 13:57

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,852
×1,722
×303
×36
×29

question asked: 21 Jan '18, 17:32

question was seen: 267 times

last updated: 05 Feb '18, 13:57