Количество положительных целых чисел в [1,1e18], которые нельзя разделить ни на какие целые числа в [2,10]

У меня возникли трудности при попытке решить следующую проблему:

Для Q запросов, Q ‹= 1e6, где каждый запрос представляет собой положительное целое число N, N ‹= 1e18, найдите количество целых чисел в [1,N], которые нельзя разделить на целые числа в [2,10] для каждого запроса.

Я подумал об использовании метода решета для фильтрации чисел в [1,1e18] для каждого запроса (аналогично решету Эратосфена). Однако значение N может быть очень большим. Следовательно, я никак не мог использовать этот метод. Самое полезное наблюдение, которое я мог сделать, это то, что числа, оканчивающиеся на 0,2,4,5,6,8, недействительны. Но это не помогает мне с этой проблемой.

Я видел решение похожей проблемы. который использует меньшее количество запросов (Q ‹ = 200). Но это не работает для этой проблемы (и я не понимаю этого решения).

Может ли кто-нибудь посоветовать мне, как решить эту проблему?


algorithm number-theory
person Donald    schedule 15.11.2017    source источник
comment
принадлежит math.stackexchange.com   -  person Jason S    schedule 15.11.2017

Ответы (2)


arrow_upward
3
arrow_downward

Единственными материальными числами в [2,10] являются те простые числа, которые равны 2, 3, 5, 7

Итак, допустим, число не может быть разделено на целые числа в [2,10], если число не может быть разделено на {2,3,5,7}

Что также равно общему числу между [1,n] минус все числа, которые делятся на любую комбинацию {2,3,5,7}.

Итак, самое интересное: из [1,n] сколько чисел делится на 2? Ответ n/2 (почему? просто, потому что каждые 2 числа есть одно число, деленное на 2)

Аналогично, сколько чисел делится на 5? Ответ n/5...

Итак, у нас уже есть ответ? Нет, так как мы обнаружили, что мы удвоили количество тех чисел, которые делятся на {2, 5} или {2, 7} ..., так что теперь нам нужно их вычесть.

Но подождите, кажется, что мы удваиваем минус те, которые делятся на {2,5,7}... так что нам нужно добавить это обратно

...

Продолжайте делать это до тех пор, пока не будут обработаны все комбинации, поэтому должно быть 2 ^ 4 комбинации, всего 16, что довольно мало для обработки.

Взгляните на принцип включения-исключения для лучшего понимания.

Удачи!

person Pham Trung    schedule 15.11.2017
comment
+1 Спасибо за объяснение! Теперь я понимаю код. TLE был вызван тем, что код, на который я ссылался в своем посте, сбрасывал вывод по каждому запросу. - person Donald; 15.11.2017

arrow_upward
0
arrow_downward

Вот подход к тому, как справиться с этим.

Для начала нужно подумать о том, как можно разделить это на части. В такой задаче следует начать с наименьшего общего знаменателя (LCD) — в данном случае 2520 (наименьшее число, которое делится на все числа меньше 10).

Идея состоит в том, что если x не делится ни на одно число от 2 до 10, то x + 2520 также не делится.

Следовательно, вы можете разделить проблему на две части:

  1. Сколько чисел от 1 до 2520 являются «относительно простыми» с числами от 2 до 10?
  2. Сколько раз 2520 входит в ваше целевое число? Необходимо учитывать и остаток.
person Gordon Linoff    schedule 15.11.2017
comment
@user3386109 . . . Я на самом деле понимаю оптимизации, которые могут быть сделаны по проблеме. Идея заключалась в том, чтобы дать ОП подход к ее решению. - person Gordon Linoff; 15.11.2017