10378. Unexpressed

One integer n is given. How many integers between 1 and n (inclusive) are unrepresentable as a^b, where a and b are integers not less than 2?

Input. One positive integer n (1 ≤ n ≤ 10¹⁰).

Output. Print the amount of unrepresentable numbers.

Sample input 1	Sample output 1
8	6
Sample input 2	Sample output 2
100000	99634

SOLUTION

data structures - set

Algorithm analysis

The number of non-representable numbers is

n – the amount of numbers representable in the form a^b

Find all numbers representable as a^b, where a > 1, b > 1, a^b ≤ n. There are not many such numbers, so all of them can be generated and stored in a container. The powers can contain repetitions, for example 2¹², 4⁶ and 16³. Duplicate numbers should be removed, so we’ll use set as a container.

Generate the powers a^b, where a = 2, 3, 4,…, . For each value of a, iterate over b = 2, 3, 4, ... until the power is not greater than n. For example:

· powers of two 2², 2³, 2⁴, … ≤ n;

· powers of three 3², 3³, 3⁴, … ≤ n;

· powers of four 4², 4³, 4⁴, … ≤ n;

Example

In the interval [1; 8] there are two numbers representable as powers: 2² = 4 and 2³ = 8. Thus, there will be 8 – 2 = 6 unrepresentable numbers.

Let n = 50. Then the following powers will be generated:

· 2² = 4, 2³ = 8, 2⁴ = 16, 2⁵ = 32 (2⁶ = 64 > 50);

· 3² = 9, 3³ = 27 (3⁴ = 81 > 50);

· 4² = 16 (4³ = 64 > 50);

· 5² = 25 (5³ = 125 > 50);

· 6² = 36 (6³ = 216 > 50);

· 7² = 49 (7³ = 343 > 50);

Note that 2⁴ = 16 and 4² = 16, however, duplicates in the set will be deleted. For n = 50, the set s will have the form: {4, 8, 9, 16, 25, 27, 32, 36, 49}. The number of unrepresentable numbers in the interval [1; 50] is 50 – s.size() = 50 – 9 = 41.

Algorithm realization

Declare a set s.

#define ll long long

set<ll> s;

Read the value of n.

scanf("%lld", &n);

Iterate through the base of the power a.

for (a = 2; a * a <= n; a++)

{

Initialize x = a². Then in the variable x iterate over the powers of number a: a³, a⁴, … . Insert the generated powers into the set s.

ll x = a * a;

while (x <= n)

{

s.insert(x);

x *= a;

}

}

The value of s.size() contains the amount of numbers that can be represented as a^b. Print the answer n – s.size().

printf("%lld\n", n - s.size());

Java realization

import java.util.*;

class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

TreeSet<Long> s = new TreeSet<Long>();

long n = con.nextLong();

for (long a = 2; a * a <= n; a++)

{

long x = a * a;

while (x <= n)

{

s.add(x);

x *= a;

}

}

System.out.print(n - s.size());

con.close();

}

}