Числа и делимость

Блог пользователя Droom

Числа и делимость

Автор Droom, 11 лет назад, По-русски

Формулировка задачи такая: найти количество чисел в промежутке между А и Б, которые делятся на Х и при этом не содержат запретных цифр(А<=Б,X натуральные, меньше 10^11 и больше нуля). Во входных данных сначала идет Х, потом и А и Б, и в следующей строке запретные цифры(по возрастанию, без дубликатов).

Пример теста 1

2 1 20 0123456789

Пример теста 2

1 1 100000000000 0123456789

Как такое решается? Перебор, понятное дело, проходить не должен)

числа

Droom
11 лет назад
15

Комментарии (15)

Написать комментарий?

Trytrytry

11 лет назад, # |

← Rev. 2 →

А такой перебор не зайдет?

for (int i = 1; ;i++)
{
   int d = i * x; //искомое число
  if (d > B)
    break;


   if (f(d) && d >= A && d <= B) // проверим что число не содержит запретных цифр и входит в нужный интервал
     ans++;



}

→ Ответить

HolyInq

11 лет назад, # ^ |

Refactored:

for (int d = ((a+x-1)/x)*x; d<=b; d+=x)
  if (f(d)) ans++;

→ Ответить

Trytrytry

11 лет назад, # ^ |

-16

Это называется обфускация:) К тому же решение все равно TLное)

→ Ответить

sivukhin

11 лет назад, # |

← Rev. 2 →

+15

Можно для относительно небольших X <= 1e6 посчитать ответ с помощью динамики. Стандартная динамика для чисел; состояния — текущая рассматриваемая позиция, остаток от деления на X; храним в динамике количество чисел с данным состоянием.

Для больших X можно просто перебрать все числа, делящиеся на X (и проверить в лоб остальные условия).

UPD. Не учел, что наши числа должны попадать в отрезок [A; B]. Ну тогда можно добавить в динамике поле, которое указывало на то, больше/меньше/равно ли наше число, суффикса числа T соответствующей длины. Тогда данная динамика считает количество чисел <= T, делящихся на X и не содержащих запретные цифры. Чтобы получить окончательный ответ можно просто посчитать величину f(B) — f(A — 1). f(T) — значение нашей динамики.

→ Ответить

Trytrytry

11 лет назад, # ^ |

Точно при маленьких X будет TL, что-то про динамику и не подумал. Спасибо за понятное объяснение.

→ Ответить

Droom

11 лет назад, # ^ |

А можно немного подробнее с этой динамикой?

Я не то чтобы настаиваю, просто еще не понимаю так сходу. Как это решение будет отбрасывать запрещенные числа и считать количество чисел с данным состоянием?

→ Ответить

sivukhin

11 лет назад, # ^ |

← Rev. 3 →

Ну просто переберем цифру, которую мы хотим поставить на текущую позицию(перебираем только среди разрешенных чисел). Теперь, если до этого у нас было число x, то сейчас стало число x + dig * 10^pos, где pos — номер позиции, куда мы ставим нашу цифру(соответственно пересчитать остаток несложно).

Пересчет состояния больше/меньше вроде бы тоже не очень сложный. Например: если наше текущее сгенерированное число x было меньше соответствующего суффикса, и мы приписываем к нему цифру dig, которая больше чем соответствующая цифра в нашем числе, то новое число будет больше соответствующего суффикса. Ну и остальные варианты аналогично.

UPD. Ну а теперь мы из некоторого состояния [pos][mod1][eq1] хотим перейти в состояние [pos + 1][mod2][eq2]. Ну т.е. количество чисел со вторым состоянием увеличилось на количество чисел с первым состоянием (dp[pos + 1][mod2][eq2] += dp[pos][mod1][eq1]). eq — состояние больше/меньше

→ Ответить

bidzilya

11 лет назад, # ^ |

← Rev. 2 →

Разве такое решение уложится в TL? взять, к примеру, тест: 1 1 10^11. Ваша динамика найдет 10^6 чисел, останется еще 10^11-10^6 ~ 10^11, многовато для перебора в лоб, по-моему. Или я неправильно Вас понял?

→ Ответить

sivukhin

11 лет назад, # ^ |

Динамика найдет все решения. Запускать перебор я предлагал только в случае больших X (т.е. либо задача решается перебором, либо динамикой)

→ Ответить

bidzilya

11 лет назад, # ^ |

Окей, разобрался.

→ Ответить

CountZero

11 лет назад, # |

+22

есть еще перебор с meet in the middle. Делим число на 2 части, для каждого 0 ≤ i < X находим число легальных префиксов и число легальных суффиксов, при делении на X дающих в остатке i. Большие X и отсутствие запрещенных цифр считаем тривиально. Все получается порядка 2·10⁷ операций в худшем случае