Max GCD After Multiplying by Prime

Борис прошел в школе сразу две новых темы - наибольший общий делитель (НОД) и простые числа. В качестве домашнего задания Борису необходимо решить Т заданий следующего вида: «Даны два целых числа А и В, можно ровно один раз умножить либо А, либо В на любое простое число. Какого наибольшего значения НОД можно добиться с помощью такого умножения?» Пример:

Пусть A = 20, В = 45. НОД(20, 45) = 5
При умножении числа А на простое число 3 итоговый НОД(20 * 3, 45) = 15.
При умножении числа В на простое число 2 итоговый НОД(20, 45 * 2) = 10.
Пожалуйста, ознакомьтесь с примерами тестов и пояснениями к ним для лучшего понимания условия.
Формат ввода
В первой строке дано целое число Т (1 <= T <= 20) - количество заданий.
В каждой из следующих Т строк содержатся два целых числа А и В (1 <= А, В <= 10^12) - параметры задания.
Формат вывода
Для каждого задания выведите единственное целое число - наибольшее значение НОД.

пример: 3 5 1 12 54 500100 100500

вывод: 5 18 500100 которого можно добиться умножением одного из чисел А и В на любое простое число.

реши на питоне

Для решения задачи, нам нужно найти наибольший общий делитель (НОД) двух чисел A и B после того, как одно из них будет умножено на простое число.

Основная идея заключается в следующем:

1. Вычислить НОД(A, B).
2. Найти все простые делители A и B.
3. Для каждого простого делителя:
   • Умножить A на этот делитель и вычислить новый НОД с B.
   • Умножить B на этот делитель и вычислить новый НОД с A.
4. Сравнить все полученные значения НОД и выбрать максимальное.

Вот реализация на Python:

import math
from functools import reduce
from sympy import primerange

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def prime_factors(n):
    factors = set()
    # Check for number of 2s that divide n
    while n % 2 == 0:
        factors.add(2)
        n //= 2
    # n must be odd at this point, so a skip of 2 (i.e., i = i + 2) can be used
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            factors.add(i)
            n //= i
    # This condition is to check if n is a prime number greater than 2
    if n > 2:
        factors.add(n)
    return factors

def max_gcd_after_multiplication(A, B):
    original_gcd = gcd(A, B)
    max_gcd = original_gcd
    
    # Get prime factors of A and B
    primes_A = prime_factors(A)
    primes_B = prime_factors(B)
    
    # Check for each prime factor of A
    for p in primes_A:
        max_gcd = max(max_gcd, gcd(A * p, B))
    
    # Check for each prime factor of B
    for p in primes_B:
        max_gcd = max(max_gcd, gcd(A, B * p))
    
    return max_gcd

# Input reading
T = int(input())
results = []
for _ in range(T):
    A, B = map(int, input().split())
    results.append(max_gcd_after_multiplication(A, B))

# Output results
for result in results:
    print(result)

Объяснение кода:

1. Функция gcd: Вычисляет НОД двух чисел с помощью алгоритма Евклида.
2. Функция prime_factors: Находит все простые делители числа n.
3. Функция max_gcd_after_multiplication:
   • Сначала вычисляет оригинальный НОД.
   • Затем находит простые делители для A и B.
   • Для каждого простого делителя A умножает A на этот делитель и вычисляет НОД с B.
   • Аналогично для простых делителей B.
   • Возвращает максимальное значение НОД.
4. Основной блок: Читает входные данные, вызывает функцию для каждого теста и выводит результаты.

Этот код должен корректно решать задачу для заданных ограничений.