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

×

LETSTOSS - Editorial

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.

This question is marked "community wiki".

asked 08 Mar '16, 22:31

deathsurgeon's gravatar image

3★deathsurgeon
112
accept rate: 0%

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,684
×3,768
×1,186
×301
×199
×23
×1

question asked: 08 Mar '16, 22:31

question was seen: 1,083 times

last updated: 08 Mar '16, 22:31