LETSTOSS - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Contest

Practice

Author: Rupesh Maity

Tester: Sarvesh Mahajan

Editorialist: Rupesh Maity

DIFFICULTY:

EASY

PREREQUISITES:

Sieve, Math

PROBLEM:

Given two integers L and R, find the number of integers between them in whose prime factorization, the count of odd powers is strictly greater than the count of even powers.

QUICK EXPLANATION:

Find all the primes till 107. For each of these primes, find their multiples in that range and calculate its power for each of the multiples. The only prime factors left are the ones greater than 10^7. There can be a maximum of one such prime factor which can have a maximum power of 1 and thus can be handled directly.

EXPLANATION:

Generate all primes till 107. You can use sieve of Eratosthenes to do this. Initialize an array num[R-L+1] with elements [L,R]. Take an array cnt[R-L+1] and initialize all its elements to 0. This cnt[] represents “count of odd powers - count of even powers” for each of the elements in our range.

For each of the primes P till 107, iterate only through all the multiples of P in num[] and find the power k for this multiple. Thus, Pk is present in the prime factorization of num[i]. If k is odd, add 1 to cnt[i] else subtract 1 from cnt[i]. Now, divide num[i] by Pk denoting that the powers of P have been removed from this number.

Now all the numbers in num[] which have not been reduced to 1 are the ones in whose prime factorization a prime factor greater than 107 is present. Remember, the product of two prime factors greater than 107 will give us a number greater than 1014, which is out of our constraints. Also, the highest power of such a prime factor is 1 for numbers till 1014 as for (P > 107) we cannot have (P2 < 10^14). Thus, for each num[i] != 1, we are left with only one P1 in its prime factorization. Here the power is 1, which is an odd number. So, for all num[i] != 1, subtract 1 from cnt[i]. Now count all the cases where cnt[i] is positive. This is our answer. For better undertanding, check the Author’s solution.

Author’s Solution:

Author’s solution can be found here.