решите задачу на питоне
Python 3.1
Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален.
Ограничение по времени выполнения программы - 1 секунда, ограничение по используемой памяти - 64 мегабайта.
Входные данные
Во входном файле записано натуральное число N (2≤N≤109)
Выходные данные
В выходной файл выведите два искомых числа A и B. Если решений несколько, выведите любое из них.
Примеры
входные данные
15
выходные данные
5 10
входные данные
16
выходные данные
8 8
Python 3.1
Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален.
Ограничение по времени выполнения программы - 1 секунда, ограничение по используемой памяти - 64 мегабайта.
Входные данные
Во входном файле записано натуральное число N (2≤N≤109)
Выходные данные
В выходной файл выведите два искомых числа A и B. Если решений несколько, выведите любое из них.
Примеры
входные данные
15
выходные данные
5 10
входные данные
16
выходные данные
8 8
More Questions From This User See All
Answers & Comments
Ответ:
Объяснение:
Если A, B имеют общий делитель d, то и A + B делится на d. Отсюда идея: найдем наибольший делитель N, меньший N, и представим всё в виде d + (N - d). d будем искать так: найдём наименьший делитель q, не равный 1 (если число составное, он не больше корня из N), тогда d = N/q.
var
q, d, n: longint;
isfound: boolean;
begin
readln(n);
isfound := false;
for q := 2 to trunc(sqrt(n)) + 1 do
if n mod q = 0 then
begin
d := n div q;
write(d, ' ', n - d);
isfound := true;
break;
end;
if not isfound then
write(1, ' ', n - 1);
end