10378. Непредставимые

Задано натуральное число n. Сколько чисел от 1 до n (включительно) непредставимы в виде a^b, где a и b – натуральные числа, не менее 2?

Вход. Одно натуральное число n (1 ≤ n ≤ 10¹⁰).

Выход. Выведите количество непредставимых чисел.

Пример входа 1	Пример выхода 1
8	6
Пример входа 2	Пример выхода 2
100000	99634

РЕШЕНИЕ

структуры данных - set

Анализ алгоритма

Количество непредставимых чисел равно

n – количество чисел, представимых в виде a^b

Найдем все числа, представимые в виде a^b, где a > 1, b > 1, a^b ≤ n. Таких чисел немного, так что их всех можно сгенерировать и сохранить в контейнер. Степени будут повторяться, например 2¹², 4⁶ и 16³. Повторы чисел следует удалять, поэтому в качестве контейнера выберем множество set.

Будем генерировать степени a^b, где a = 2, 3, 4, …, . Для каждого значения a перебираем b = 2, 3, 4, … пока степень не больше n. Например:

· степени двойки 2², 2³, 2⁴, … ≤ n;

· степени тройки 3², 3³, 3⁴, … ≤ n;

· степени четверки 4², 4³, 4⁴, … ≤ n;

Пример

На промежутке [1; 8] имеются два числа представимые в виде степеней: 2² = 4 и 2³ = 8. Таким образом непредставимых будет 8 – 2 = 6 чисел.

Пусть n = 50. Тогда будут сгенерированы следующие степени:

· 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);

Заметим, что 2⁴ = 16 и 4² = 16, однако во множестве дубли удалятся. Для n = 50 множество s будет иметь вид: {4, 8, 9, 16, 25, 27, 32, 36, 49}. Количество непредставимых чисел на промежутке [1; 50] равно 50 – s.size() = 50 – 9 = 41.

Реализация алгоритма

Объявим множество s.

#define ll long long

set<ll> s;

Читаем входное значение n.

scanf("%lld", &n);

Перебираем основание степени a.

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

{

Инициализируем x = a². Далее в переменной x перебираем степени числа a: a³, a⁴, … . Заносим сгенерированные степени во множество s.

ll x = a * a;

while (x <= n)

{

s.insert(x);

x *= a;

}

}

Значение s.size() содержит количество чисел, представимых в виде a^b. Выводим ответ, равный n – s.size().

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

Java реализация

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();

}

}