Задача
Заданы целые неотрицательные числа $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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> using namespace std; int main() { long long int a,b,x,k; cin >> a >> b >> x; k =b/x - a/x; if (!(a%x)) k++; cout << k; return 0; } |
Решение
Объявим переменные a, b, x и k типа long long int, где a, b и 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 на единицу.
Ссылки