CCC '09 S1 - Cool Numbers

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 64M

Problem type
Canadian Computing Competition: 2009 Stage 1, Senior #1

Eric likes interesting numbers like 64. It turns out that 64 is both a square and a cube, since 64 = 8^2 and 64 = 4^3. Eric calls these numbers cool. Write a program that helps Eric figure out how many integers in a given range are cool.

Input Specification

On the first line of input, you are given an integer a such that a \ge 1 and a \le 10^8. On the second line of input, you are given an integer b such that b \ge a and b \le 10^8.

Output Specification

The output should be the number of cool numbers in the range a to b (inclusively: that is, a and b would count as cool numbers in the range if they were actually cool).

Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2



  • 1
    nicholaskidston  commented on Dec. 2, 2021, 1:52 p.m.

    tips to not get TLE on c++?

    • 2
      Ankit_04  commented on Dec. 4, 2021, 6:50 p.m. edited

      Try to find cool numbers without going through every number in the range of the lower and upper bounds. It may help to take into account that if a number is a square and a cube, then it can also be represented as x^6. Hope that helps :D

  • 1
    eliaskountouris  commented on June 12, 2020, 1:09 a.m.

    I get floating-point errors for test case 3 only on the online judge. On my machine, it works properly.

    Online judge outputs 0, my machine outputs 1 which is the correct answer to that test case.

    Any thoughts on how to fix? Is it just an issue with the judge or is it my code thats the problem here?

  • 15
    singbeilii  commented on Dec. 19, 2019, 1:15 a.m.

    Everyone remember a^6 is contained as a^2 and a^3

  • -2
    andraantariksa  commented on June 2, 2019, 1:53 p.m.

    You don't have to check all of the integer. Remember that the cube numbers (1, 8, 27, 64) will be less than square numbers (1, 4, 9, 16, 25, 36, 49, 64, 81, 100) in a range ([1-100]) :) .

    There's no such formula to solve this in O(n) AFAIK, but there's a formula to know the total of square number in a given range (You can't use it for this problem).

    By the way, I'm using Haskell :) .

    • 7
      Evanhyd  commented on Dec. 2, 2020, 8:43 p.m.

      There are truly "no such formulas to solve this in O(n)", because everyone here is using O(1) "formula"

  • 0
    tangential  commented on Feb. 13, 2019, 3:03 a.m.

    Test case three is screwing me up. I first had problems with 2 and 5, and now it's 3.

    I didn't use for loops or anything. I just did math floor and math ceiling with the 6th root of inputs b and a, respectively.

    Any help?

    • 0
      Moana  commented on March 19, 2020, 1:45 a.m.

      Test case 3 contains 1771561, which is 11⁶. pow(1771561,1./6) will give you 10.999999999999998.

    • 0
      geese  commented on Feb. 14, 2019, 10:05 a.m.

      You are getting baited by a floating point

  • -4
    Xenosi  commented on Feb. 2, 2019, 1:57 p.m. edited

    This problem is a pain with python .-.

    • -4
      Arihan10  commented on Feb. 2, 2019, 7:18 p.m.

      Agreed, time limit for Python is way too narrow.

      • 5
        geese  commented on Feb. 6, 2019, 11:22 a.m.

      • -2
        kingW3  commented on Feb. 3, 2019, 9:04 a.m. edited

        Not really, the algorithm is the problem, this can be done in constant time it can also be done slower than constant but faster then O(n).

        • -3
          Xenosi  commented on March 17, 2019, 1:23 p.m. edit 2

          I used kind of a cheap way to do it(w/ python), but I personally think this is harder with Python than with compiled languages.

  • -7
    Arihan10  commented on Jan. 25, 2019, 7:48 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.

    • 12
      Robloxian  commented on Jan. 26, 2019, 5:04 p.m.

      You can make your code run faster by not using python

      • -6
        Arihan10  commented on Jan. 26, 2019, 6:40 p.m.

        This comment is hidden due to too much negative feedback. Show it anyway.

        • 3
          Riolku  commented on Jan. 28, 2019, 9:12 a.m.

          C++ is a compiled language, while python is an interpreted language. The latter is almost always slower. Although PyPy interprets code into assembly, it is still much slower than C++.

    • -2
      magicalsoup  commented on Jan. 25, 2019, 11:29 p.m.

      This requires a bit more knowledge in math, I suggest you looking up exponent laws

      • -1
        Arihan10  commented on Jan. 26, 2019, 4:34 p.m. edit 3

        Yeah, but even so, won't I still have to iterate through every number in the list (which is, I think, except for the language, the main reason I am getting a TLE.)?

        • 2
          magicalsoup  commented on Jan. 29, 2019, 4:10 p.m.

          you can be more efficient, you can constant optimize in alot of places

          • 3
            Darcy__Liu  commented on Jan. 31, 2019, 7:23 p.m.

            Actually the intended solution for this question has nothing to do with constant optimization. Even with a bad constant factor, you still should easily be able to pass this question.

            I think you might be mixing up constant optimization vs. optimization of your time complexity

  • -2
    MacShack  commented on April 26, 2018, 10:53 a.m.

    Can't figure out what I can make faster, but cases 2 and 5 say I exceeded the time limit.

    • 1
      Beautiful_Times  commented on April 27, 2018, 9:58 a.m.

      There is a faster way of finding cool numbers other than checking through the entire range and checking if every number in the range is a cool number.

    • 0
      account_disabled  commented on April 27, 2018, 8:31 a.m.

      Could you be more specific? What is your approach?

  • -1
    Dordor1218  commented on Feb. 19, 2018, 6:40 p.m.

    What's wrong with my code! i tried it on my computer and it works perfectly but test case 2 & 5 are wrong

    • -1
      KevinLu  commented on Feb. 19, 2018, 6:47 p.m.

      Check your for loop and try using long instead of int.

      • -1
        Dordor1218  commented on Feb. 19, 2018, 8:50 p.m.

        its still wrong

        • 2
          wleung_bvg  commented on Feb. 20, 2018, 10:19 a.m.

          Your program is appears to have floating point precision errors (comparing doubles is inaccurate). There are ways to handle this issue, and also a way to avoid this issue entirely.

      • 1
        Dordor1218  commented on Feb. 19, 2018, 8:48 p.m.

        ok thx