e-olymp 8594. Между A и B

Задача

Заданы целые неотрицательные числа $a$ и $b$ [latex](a \le b)[/latex] и натуральное число $x$. Сколько существует чисел между $a$ и $b$ включительно, делящихся на $x$?

Входные данные

Три числа $a$, $b$ и $x$ [latex](0 \le a \le b \le 10^{18}, 1 \le x \le 10^{18}[/latex]).

Выходные данные

Выведите ответ на задачу.

Тесты

Вход Выход
2 6 5 1
1 200 3000 0
83 180 10 10
775 12004 312 36
13 42 7 5

 Код программы

Решение

Объявим переменные abx и k   типа  long long int, где   ab и x — соответствующие числа из условия, а  k — количество чисел на промежутке [latex][a, b][/latex].

Для начала, обоснуем эквивалентность деления и нахождения количества кратных чисел на промежутке [latex][0, n][/latex] . Действительно, деление — это действие, по которому можно узнать сколько раз делитель содержится в делимом. А так как числа, кратные $x$, на промежутке [latex][0, n][/latex] встречаются начиная с $x$ с периодичностью $x$, то количество кратных чисел на промежутке является количеством вместимых $x$ в $n$. Эквивалентность доказана.

Тогда, разность количеств кратных $x$ чисел на промежутках [latex][0, b][/latex] и [latex][0, a][/latex] будет количеством таких чисел на полуинтервале [latex](a, b][/latex], так что придётся отдельно проверять, является ли $a$ кратным $x$, и в таком случае увеличивать k на единицу.

Ссылки

e-olymp

ideone

 

18 thoughts on “e-olymp 8594. Между A и B

  1. Вы просматриваете три варианта и два из них имеют один и тот же результат, их можно объединить

  2. Здесь изложена куча условий, в которых довольно легко ошибиться и не очевидно, что они правильные. В то же время к данной задаче есть классический и более простой подход. «Научимся считать количество чисел, делящихся на $х$, от 1 до $k$…»
    Пока что предоставлю Вам сделать из этого посыла самостоятельные выводы.

      • Никаких претензий, только советы 🙂

        Хорошо, поясняю. Описание Вашего решения напоминает процесс блуждания: возьмем что-то похожее на ответ, зашлем на сервер, получим Wrong Answer, а точно! есть еще случай, добавим для него if, снова зашлем, снова WA… Вот, теперь ОК, так и оставим.

        Если бы у Вас под рукой не было сервера, или на сервере были бы неполные тесты, то из данного Вами описания было бы невозможно сделать вывод, что именно данный набор проверок является достаточным и почему. Вдруг Ваша формула еще какой случай «не видит» или в уже рассмотренных случаях какой-то неверно описан.

        На самом деле, проблема кроется в необоснованности самого первого утверждения «Для решения данной задачи, мы должны найти длину отрезка [a, b]». Ведь, как Вы показываете далее, всязь между длиной отрезка и количеством делящихся на x чисел неоднозначна. Я предлагаю вместо этого научиться считать сколько чисел от 1 до k делится на x. Там все однозначно. Тогда можно найти количество на отрезке, как разность количеств на двух отрезках. Этот подход проще и является традиционным для таких задач.

          • Почти все хорошо. Вы все-таки не избежали одной проверки, а могли бы, если бы заметили, что нам из отрезка [1; b] нужно выбросить в точности отрезок [1; a-1]

          • На комментарий 20.11.18.
            Я пробовал рассмотреть вариант, когда отрезок [1; а-1]. Но на сервере он не проходит полностью. Возможно, я что то сделал не так.

          • Проблема может возникнуть с отрезком, начинающимся с 0. Потому что -1/x обрезается вверх (к 0), а не вниз. Если бы a-1 всегда были неотрицательными, все бы работало правильно.

            Можно a и b предварительно увеличить на х. Тогда их остатки от деления на х не изменятся, а требование неотрицательности будет выполнено. Но с другой стороны, это решение годится для a >= 0 и не годится для a >= -10^18, т.е. не является универсальным.

            Более универсальным было бы прибавить к границам что-то в духе (-a / x + 1) * x. Но не уверен, что в данной задаче стоит так заморачиваться.

            Еще можно делить всегда в меньшую сторону.
            int myDiv(int p, int q) {p -= (p % q + q) % q;return p / q;}

            Интересно, какой вариант больше нравится Игорю Евгеньевичу.

          • Я разделяю Ваш интерес в поиске универсального решения. Вы дали мне тему для размышления. Благодарю.
            Также я поддерживаю ваши сомнения, касательно того, нужно ли модифицировать правильное решение, занимаясь преждевременной оптимизацией.

          • Поясню причину своих сомнений. Данная задача не является самостоятельной. Она демонстрирует распространенный прием, который в качестве вспомогательного применяется во многих куда более сложных задачах. Это важно уметь писать с минимально возможным количеством ифов. т.к. если у Вас будет не отрезок, а 4-мерный гиперкуб чисел и в нем еще надо будет применять формулу включения-исключения, то каждый +иф это потенциальный +баг. Так что я задумался, какой подход позволил бы писать максимально универсальный и при этом не слишком усложненный код. Пока что это не очевидно.

  3. Саша, Вы никак не реагируете на советы и замечания. Просто снова и снова ставите работу на проверку. Какой реакции с моей стороны Вы ожидаете? Что мне это надоест и я просто зачту?
    Если не понимаете сути замечаний, задавайте вопрос. Если понимаете — исправляйте.

  4. Посмотрел своё решение. Я тоже, как советует Олег, отдельно обрабатывал случай с нулевой левой границей.

    Конечно, можно выкрутиться и сразу исключить 0, если сдвинуть всю шкалу вправо так, чтобы это не влияло на ответ:

  5. Действительно… это действительно работает без ветвлений. Спасибо. Надеюсь вы не злитесь, за то, что я проверил ваш код на сервере?

Добавить комментарий