ПАСКАЛЬ. Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален. Входные данные Во входном файле INPUT.TXT записано нату...

ПАСКАЛЬ. Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален. Входные данные Во входном файле INPUT.TXT записано натуральное число N (2<=N<=109) Выходные данные В выходной файл OUTPUT.TXT выведите два искомых числа A и B. Если решений несколько, выведите то из них, где A принимает наименьшее возможное значение.
Гость
Ответ(ы) на вопрос:
Гость
Если 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.
Не нашли ответ?
Ответить на вопрос
Похожие вопросы