Optimizing GCD Calculation with Prime Factors

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

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

мои входные данные очень большие, разве нет никакого способа оптимизировать этот код?

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

long long gcd(long long x, long long y) {
    while (y) {
        long long temp = x % y;
        x = y;
        y = temp;
    }
    return x;
}

bool is_prime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

long long max_gcd_after_multiplication(long long A, long long B) {
    long long original_gcd = gcd(A, B);
    long long max_gcd = original_gcd;
    
    for (long long p = 2; p <= max(A, B); p++) {
        if (is_prime(p)) {
            max_gcd = max({max_gcd, gcd(A * p, B), gcd(A, B * p)});
        }
        if (max_gcd == max(A, B)) break;
    }
    
    return max_gcd;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    vector<long long> results;
    for (int i = 0; i < T; i++) {
        long long A, B;
        cin >> A >> B;
        results.push_back(max_gcd_after_multiplication(A, B));
    }
    
    for (long long result : results) {
        cout << result << "\n";
    }
    
    return 0;
}

Ваш код можно оптимизировать, чтобы избежать избыточных вычислений и улучшить производительность. Основная идея заключается в том, что вам не нужно проверять все числа до max(A, B) на простоту. Вместо этого вы можете использовать простые числа, которые делят gcd(A, B), и их кратные.

Вот оптимизированный подход:

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

Вот как это может выглядеть в коде:

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

long long gcd(long long x, long long y) {
    while (y) {
        long long temp = x % y;
        x = y;
        y = temp;
    }
    return x;
}

vector<long long> get_prime_factors(long long n) {
    vector<long long> factors;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            factors.push_back(i);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
    return factors;
}

long long max_gcd_after_multiplication(long long A, long long B) {
    long long original_gcd = gcd(A, B);
    long long max_gcd = original_gcd;

    // Получаем простые делители НОД
    vector<long long> prime_factors = get_prime_factors(original_gcd);
    
    for (long long p : prime_factors) {
        max_gcd = max(max_gcd, gcd(A * p, B));
        max_gcd = max(max_gcd, gcd(A, B * p));
    }
    
    return max_gcd;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    vector<long long> results;
    for (int i = 0; i < T; i++) {
        long long A, B;
        cin >> A >> B;
        results.push_back(max_gcd_after_multiplication(A, B));
    }
    
    for (long long result : results) {
        cout << result << "\n";
    }
    
    return 0;
}

Объяснение изменений:

1. Функция get_prime_factors: Эта функция находит все простые делители числа n. Это позволяет избежать проверки всех чисел до max(A, B) на простоту.
2. Использование простых делителей: Вместо проверки всех простых чисел, мы используем только простые делители gcd(A, B), что значительно уменьшает количество необходимых вычислений.
3. Упрощение логики: Мы сразу обновляем максимальное значение НОД, используя найденные простые делители.

Этот подход значительно ускоряет выполнение программы, особенно для больших значений A и B.