Problem Statement
定义了一种半完美数,一个数 n 被称为半完美数当且仅当存在 a、b、c 三个整数使得 b > 1, 1 ≤ c < a, n = c * a ^ b 。
现给出一个区间 [L, R] 之间有多少个半完美数。
1 ≤ L, R ≤ 8 * 10,000,000,000,000,000
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.