printЛето 1

printC. Квадратный корень

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Известно, что квадратные корни из многих натуральных чисел являются иррациональными числами. Поэтому их нельзя точно представить рациональным числом `p/q`. Однако можно подобрать такое рациональное число, что погрешность `|sqrt(N)\ -\ p/q|` будет сколь угодно малой. Ваша задача – по заданному натуральному `N` найти рациональное число `p/q` минимально отличающееся от `sqrt(N)`, при этом знаменатель `q` не должен превосходить заданного числа `Q`. Не забудьте, что ваш ответ должен быть несократимой дробью!
Ввод
Во входном файле записаны два натуральных числа `N` и `Q` (`1\ ≤\ N,\ Q\ ≤\ 10^6`).
Вывод
Запишите в выходной файл числитель `p` и знаменатель `q` найденной несократимой дроби, которая наименее отличается от `sqrt(N)`.

Пример ввода 1

1 1

Пример вывода 1

1 1

Пример ввода 2

4 1000

Пример вывода 2

2 1

Пример ввода 3

3 100

Пример вывода 3

168 97
Источник: Весенний турнир Мартовского зайца, 2008
loading