Найдите, сколько чисел являются идеальными квадратами, и sqrt () - простое число в диапазоне L, R

Question

Прежде всего, не стесняйтесь улучшить форматирование вопроса

Этот вопрос уже решен Госвином фон Бредерлоу!

Здравствуйте, я восхищаюсь программирование и эта проблема столкнулась, и я не знаю, как лучше всего решить эту проблему:

Вопрос имеет T тестовых случаев, который состоит из:

Учитывая диапазон L и R, найдите, сколько чисел соответствуют ограничениям:

i) Число - идеальный квадрат;

ii) sqrt (Число) - простое число.

Ограничения:

1 <= T <= 1e4 </p>

1 <= L, R <= 1e12 </p>

Ограничение по времени: 1 секунда

Итак, я попробовал это с простой идеей предварительной обработки с unodered_map (lld, bool) всеми ответами с ситом eratosthenes для каждого sqrt (Number), учитывая, что Number является идеальный квадрат

После того, как я передаю диапазон pow (sqrt (l), 2) и увеличиваю его до следующего нечетного числа ... как: 4 9 16 25, разница составляет o номера дд: 5 7 9 ...

Мой код:

long long int l, r; scanf("%lld %lld", &l, &r);
long long int odd = ceil(sqrt(l)), n = odd*odd;
odd = (2*odd) + 1;
long long int ans = 0;
while((n >= l && n <= r)){
    it = h.find(n);
    ans = ans + it->second;
    n = n + odd; 
    odd = odd + 2;
}

Но я все еще получил TLE, мне нужна помощь, ребята, спасибо!

Answer 1

Единственный вопрос, который я вижу, заключен в следующем: «Я не знаю, как лучше всего решить эту проблему».

Ваш путь, кажется, уже достаточно умен. У вас есть ошибки, даже в вставленном вами фрагменте кода. Похоже, вы вычисляете сумму чисел вместо того, чтобы считать их.

Одна вещь, которую я мог бы улучшить, это сам подсчет. Похоже, у вас есть таблица ха sh всех квадратов простых чисел, и вы просто проверяете все auqares, если они есть в таблице.

Почему бы не сделать сбалансированное дерево из простых чисел? В каждом узле вы храните минимальное и максимальное количество и количество для поддерева. Листья будут (n, n, 1), где n является одним из квадратов простых чисел. С учетом L и R вы можете затем go через дерево и суммировать все поддеревья, которые находятся в интервале, и перейти в поддеревья, которые только частично находятся внутри. Игнорировать все на улице. Это должно добавить логарифмический коэффициент c к вашей сложности.