НачалоПодразделы
Другие разделы
| 927. Номера |
| 928. Снова номера |
| 930. Галактика |
| 931. Дорога |
| 932. Per aspera ad astra |
| 933. Последовательность |
| 934. Сложение |
| 935. Отрезок |
Дата и время
23/11/2024 20:42:36
929. Квадратный корень
Квадратный корень
Дерево Штерна-БрокоОлимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 - 1 (C) |
| 03/07/2008 | Лето 2008 дорешивание ( 1C) |
| 09/09/2014 | Занятие 2 (B) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
