Республиканская олимпиада по информатике, 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 ($0 \le A, C, L, R \le 10^9$).

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

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

Примеры:

1.Вход:

21 5 1 21

Ответ:

2

2.Вход:

32443 463 457 3716

Ответ:

12

Оценивание:

Баллы выдаются пропорционально количеству пройденных тестов.:
Не менее 25% тестов с ограничениями $0 \le R - L \le 10^6$. ( Ескендір Сұлтанов )

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

[deleted.]

Заметим, что если $A \equiv C \, (mod \, B)$, где $C$ остаток, то $C<B$ и $A - C \, \vdots \, B$. Значит нам достаточно итерировать через все делители $n = A - C$ и проверять условия $L \leq b \leq R$ и $C < b$. Для эффективности будем делили искать по парам, (учитывая возможность $n= i^2$) от $1$ до $\sqrt{n}$.

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

#include <bits/stdc++.h>

using namespace std;

int main(){
    int  a, c, l, r;
    cin >> a >> c >> l >> r;
    int n = a-c;
    int count = 0;
    for (int i=1; i<=sqrt(n); i++) 
    { 
        if (n%i == 0) 
        { 
            if(l<=i && i <=r && i>c ){
                count++;
                }
            if(n/i != i && l<=n/i && n/i <=r && n/i>c){
                count++;
                }   
        } 
    } 
    
    cout << count;
    
    
    }

[deleted.]