Connection Status:
Competition Arena > SemiPerfectPower

SemiPerfectPower

SRM 582 · 2012-12-13 · by semiexp

SRM 582 · 2012-12-13 · by semiexp · Math, Search
Class Name: SemiPerfectPower
Return Type: long
Method Name: count
Arg Types: (long long, long long)
Problem Statement

Problem Statement

Magical Girl Iris loves perfect powers. A positive integer n is a perfect power if and only if there are positive integers b > 1 and c > 1 such that b^c = n (where ^ denotes exponentiation). For example, 8 (=2^3) and 243 (=3^5) are perfect powers, while 1 and 54 are not.
One day, Iris discovered that there are very few perfect powers. To avoid being disappointed, she quickly invented the semi-perfect powers: A positive integer n is a semi-perfect power if and only if there are positive integers a >= 1, b > 1, and c > 1 such that a < b and a*(b^c) = n. For example, 243 (=1*3^5) and 54 (=2*3^3) are semi-perfect powers, while 1 and 24 are not.
Note that for some semi-perfect numbers there may be more than one corresponding triple (a,b,c). For example, 432 can be expressed as 2*6^3, but also as 3*12^2.
You are given longs L and R. Calculate and return the number of semi-perfect powers that lie between L and R, inclusive.

Constraints

  • L will be between 1 and 8*10^16, inclusive.
  • R will be between L and 8*10^16, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
18
58
Returns: 9

There are 9 semi-perfect powers between 18 and 58, inclusive: 18, 25, 27, 32, 36, 48, 49, 50, and 54.

1)
1
10
Returns: 3

Note that 1 is not considered to be a semi-perfect power.

2)
80000000000000000
80000000000000000
Returns: 1
3)
60
70
Returns: 1

The number 64 is the only semi-perfect power in the given range. Note that there are multiple ways to choose a, b, and c when showing that 64 is a semi-perfect power. Still, each semi-perfect power should only be counted once.

4)
319268319114310
35860463407469139
Returns: 95023825161

Submissions are judged against all 111 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SemiPerfectPower with a public method long long count(long long L, long long R) · 111 test cases · 2 s / 256 MB per case

Submitting as anonymous