SemiPerfectPower
SRM 582 · 2012-12-13 · by semiexp
SRM 582 · 2012-12-13 · by semiexp · Math, Search
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 givenlong s L and R.
Calculate and return the number of semi-perfect powers that lie between L and R, inclusive.
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
Constraints
- L will be between 1 and 8*10^16, inclusive.
- R will be between L and 8*10^16, inclusive.
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