Question

Решите задачу на питоне Python 3.1 Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален. Ограничение по времени выполнения программы - 1 секунда, ограничение по используемой памяти - 64 мегабайта. Входные данные Во входном файле записано натуральное число N (2≤N≤109) Выходные данные В выходной файл выведите два искомых числа A и B. Если решений несколько, выведите любое из них. Примеры входные данные 15 выходные данные 5 10 входные данные 16 выходные данные 8 8

Answer 1

Ответ:

Объяснение:

Если 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

Answer 2

Для решения этой задачи можно воспользоваться следующим алгоритмом:

1. Если N четное, то два искомых числа могут быть равными N/2. Иначе, они будут равными (N-1)/2 и (N+1)/2.
2. Выберем одно из предложенных решений.

Давайте реализуем этот алгоритм на Python:

pythonCopy code
def find_numbers_with_max_gcd(N):
    if N % 2 == 0:
        A = B = N // 2
    else:
        A = (N - 1) // 2
        B = (N + 1) // 2
    return A, B

# Ввод числа N из входного файла
N = int(input())

# Находим искомые числа A и B
A, B = find_numbers_with_max_gcd(N)

# Выводим результат в выходной файл
print(A, B)

Примечание: В приведенной реализации нет необходимости включать ограничение по времени выполнения и используемой памяти, так как решение является достаточно эффективным для данной задачи.