Loading [MathJax]/jax/output/SVG/jax.js

Республиканская олимпиада по информатике, 2015 год, 9 класс


Задача D. Помощь Жандосу

На прошлой неделе на уроке математики Жандос узнал как взять число по модулю. Определим A по модулю B как остаток от деления A на B и обозначим его как A mod B. Учитель по математике задал домашнее задание: найти количество чисел В от L до R включительно, что A mod B = C.

Жандосу нужно сделать домашнюю работу, но он хочет посмотреть футбол. Потому он обратился к вам за помощью. Напишите программу, которая по числам A, C, L, R найдет количество чисел B от L до R включительно, что A mod B = C.
Входные данные:
В единственной строке ввода даны целые числа A, C, L, R (0A,C,L,R109).
Выходные данные:
Выведите ответ на задачу.
Примеры:
1.Вход:
21 5 1 21
Ответ:
2
2.Вход:
32443 463 457 3716
Ответ:
12
Оценивание:
Баллы выдаются пропорционально количеству пройденных тестов.:
Не менее 25% тестов с ограничениями 0RL106. ( Ескендір Сұлтанов )
посмотреть в олимпиаде

Комментарий/решение:

пред. Правка 2   0
4 года 2 месяца назад #

[deleted.]

пред. Правка 3   -1
5 года 3 месяца назад #

Заметим, что если AC(modB), где C остаток, то C<B и ACB. Значит нам достаточно итерировать через все делители n=AC и проверять условия LbR и C<b. Для эффективности будем делили искать по парам, (учитывая возможность n=i2) от 1 до n.

показать/скрыть код

C++

пред. Правка 2   1
4 года 2 месяца назад #

[deleted.]