Курс: Подготовка к ЕГЭ

Модуль: B27 (C4) - анализ пар

Задачи

Задача

1/23

72. НОД для пары чисел

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Задача

Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять, какое значение А встречалось чаще всего. Если несколько значений А встречалось одинаковое наибольшее количество раз, вывести их в порядке убывания.
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 100 килобайт.

Входные данные:
На вход программе в первой строке подаётся количество пар N (1 <= N <= 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000. 
 
Ввод Вывод
6
1 3 
5 15  
6 9  
5 4  
3 3  
36 40  
3 1