Олимпиадная задача по теории чисел: восстановление номеров растений России по НОД
Задача
Все виды растений России были занумерованы подряд числами от 2 до 20000 (числа идут без пропусков и повторений). Для каждой пары видов растений запомнили наибольший общий делитель их номеров, а сами номера были забыты (в результате сбоя компьютера). Можно ли для каждого вида растений восстановить его номер?
Решение
Растения с номерами 101 и 10201 = 101² (как и с номерами 8192 = 213 и 16384 = 214) различить нельзя. Они имеют одинаковые наибольшие общие делители с любым числом, не превосходящим 20000. Поэтому воcстановить их номера не удастся.
Ответ
Нельзя.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет