Problem link
Problem setter : maazbinasad3
Problem tester: prasoonjain006
Editorialist: maazbinasad3
Difficulty:
Easy-Medium
Prerequisites :
Number theory
Problem:
Find smallest multiple of a number that can be represented as sum of consecutive odd numbers starting from 1.
Explanation:
Which numbers can be represented as sum of consecutive odd numbers from 1? Observe that they are perfect square.
How to find smallest such multiple? Problem reduces to finding smallest number that should be multiplied to N to make it perfect square.
Observe that prime factors of perfect squares occur in pairs. For example 16 = 2x2x2x2 (2 pairs of 2), 25 = 5x5 (a pair of 5). Just find prime factors that are not in pair (or count of that prime number is odd in prime factorization of N).
For instance, prime factorization of 8 is 2x2x2. Since, one of the 2 is not in pair, 2 is the minimum number that is to be multiplied with 8 to make it a perfect square. Therefore, answer is 16.