back to the menu

Flag Counter TopCoder SRM 582 - 1000: SemiPerfectPower

SRM 582 1 1000 SemiPerfectPower


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.

Definition

(be sure your method is public)

Limits

Constraints

Test cases

  1. input
    • L 18
    • R 58
    output
    Returns 9
    note
    There are 9 semi-perfect powers between 18 and 58, inclusive: 18, 25, 27, 32, 36, 48, 49, 50, and 54.
  2. input
    • L 1
    • R 10
    output
    Returns 3
    note
    Note that 1 is not considered to be a semi-perfect power.
  3. input
    • L 60
    • R 70
    output
    Returns 1
    note
    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. input
    • L 319268319114310
    • R 35860463407469139
    output
    Returns 95023825161
  5. input
    • L 1
    • R 80000000000000000
    output
    Returns 169502909978

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.