# 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 10^{7}. 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 10^{7}. 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 10^{7}, iterate only through all the multiples of P in num[] and find the power k for this multiple. Thus, P^{k} 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 P^{k} 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 10^{7} is present. Remember, the product of two prime factors greater than 10^{7} will give us a number greater than 10^{14}, which is out of our constraints. Also, the highest power of such a prime factor is 1 for numbers till 10^{14} as for (P > 10^{7}) we cannot have (P^{2} < 10^14). Thus, for each num[i] != 1, we are left with only one P^{1} 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.

asked
**08 Mar '16, 22:31**

3★deathsurgeon

11●2

accept rate:
0%