Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет.

Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не записывает. Когда утренники закончились, Деду Морозу стало интересно, сколько различных чисел встречается в записях Снегурочки. Дед Мороз и Снегурочка — волшебные, поэтому число утренников N, на которых они побывали, может быть очень большим. Напишите программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию.Желательно, чтобы программа была эффективной как по времени работы, так и по используемой памяти. Программу будем считать эффективной по памяти, если используемая память не зависит от размера входных данных (то есть числа утренников). Программу будем считать эффективной по времени, если при увеличении размера входных данных N в t раз (t — любое число) время её работы увеличивается не более чем в t раз.Описание входных данныхВ первой строке вводится одно целое положительное число — количество утренников N. Каждая из следующих N строк содержит два целых числа: сначала D — количество пришедших на очередной утренник детей, а затем K - количество конфет в мешке Деда Мороза на этом утреннике. Гарантируется выполнение следующих соотношений:1 ≤ N ≤ 100001 ≤ D ≤ 100 (для каждого D)D ≤ K ≤ 1000 (для каждой пары D, K)Описание выходных данныхПрограмма должна вывести одно число — количество различных чисел в записях Снегурочки. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.Пример входных данных:710 5815 31520 408100 100032 6332 6311 121Пример выходных данных для приведённого выше примера входных данных:2 Критерии оценивания выполнения задания | Баллы | Программа правильно работает для любых входных данных и является эффективной как по времени, так и по памяти. Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку). | 4 | Не выполнены условия, позволяющие поставить 4 балла. Программа работает верно и является эффективной по времени, но размер используемой памяти зависит от количества исходных данных. Например, входные данные (все значения D и K) запоминаются в массиве или другой структуре данных, размер которой зависит от N. Допускается одна из следующих ошибок:1) Вместо остатка от деления K на D вычисляется остаток от деления D на K.2) Отсутствует предварительная инициализация счётчиков (для языков, в которых нет гарантированного начального обнуления).3) Неверно разрешается конфликт равенства максимумов (выбирается меньшее значение индекса вместо большего).4) Неверно выводится ответ (или не выводится никакого ответа), если все остатки оказались равны нулю.Допускается наличие от одной до трёх синтаксических ошибок, описанных в критериях на 4 балла. | 3 | Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет. Возможны переборные решения, при которых все исходные данные хранятся в массиве (или в двух массивах), этот массив многократно просматривается, при каждом просмотре подсчитывается количество пар с определённым остатком. В реализации алгоритма допущено более 1 ошибки из числа перечисленных в критериях на 3 балла или допущены другие ошибки, приводящие к неверной работе программы в отдельных случаях. Допускается наличие от одной до пяти синтаксических ошибок, описанных в критериях на 4 балла. | 2 | Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Программа работает в отдельных частных случаях. Один балл также ставится, если программа написана неверно, но из описания алгоритма и общей структуры программы видно, что экзаменуемый в целом правильно представляет путьрешения задачи. | 1 | Не выполнены условия, позволяющие поставить 1, 2, 3 или 4 балла. | 0 | Максимальный балл | 4 |