Слишком долго ищет НОК больших чисел

Question

Задача состоит в том, чтобы найти НОК двух чисел, но при тесте выскакивает ошибка Time Limit.

#include <iostream>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
long long minimum = (a * b) * (a * b);
for (long long i = 1; i <= (a * b); i++){
    if ((i % a == 0) and (i % b == 0)){
        if (minimum > i){
            minimum = i;
        }
    }
}
    cout << minimum << endl;
}

Answer 1

Вот, писано по тем временам, когда еще gcd() и lcm() в стандарт не входили...

template<typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
T gcd(T m, T n)
{
    while(m && n) if (m < n) n %= m; else m %= n;
    return m + n;
}

template<typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
T lcm(T m, T n)
{
    return (m/gcd(m,n))*n;
}

Убрать шаблоны и записать для вашего long long, думаю, сумеете самостоятельно?

P.S. Кстати, даже в вашем варианте... Почему вы не выходите из цикла, обнаружив НОК? Зачем проверять дальше? И какой смысл проверять от 1, если НОК автоматом не меньше наибольшего из чисел? Да и увеличивать проверяемые значения на 1?

#include <iostream>
using namespace std;
int main()
{
    long long a, b;
    cin >> a >> b;
    if (a > b) { long long t = a; a = b; b = t; }
    for (long long i = b; i <= a * b; i += b){
        if (i % a == 0)
        {
            cout << i << endl;
            break;
        }
    }
}

Конечно, это, мягко говоря, не быстрый вариант... Но куда быстрее вашего изначального. Да и при больших значениях ваш вариант просто не будет работать из-за переполнений.

Answer 2

Тип long long означает что НОК нужно считать и для отрицательных чисел. Традиционно НОК определяется как наименьшее натуральное число, которое делится на оба аргумента функции. То есть, даже для отрицательных аргументов нужно возвращать положительный результат.

Нужно решить что возвращать если один или оба аргумента нули. НОК должен делиться на оба аргумента, а на ноль деление не определено, следовательно и НОК не определён. Чтобы не усложнять решение, доопределим НОК нулём если хотя бы один его аргумент нулевой.

НОК для аргументов со знаком: от аргументов берётся абсолютная величина, которая приводится в беззнаковый тип. Результат приводится обратно:

long long lcm(long long a, long long b) {
    return static_cast<long long>(lcm(
        static_cast<unsigned long long>(std::abs(a)),
        static_cast<unsigned long long>(std::abs(b))
    ));
}

Вся работа делается внутри беззнаковой версии. Она проверяет аргументы на нули и вычисляет НОК(a, b) = (a * b) / НОД(a, b). Порядок операций в правой части тождества изменён чтобы избежать переполнения:

unsigned long long lcm(unsigned long long a, unsigned long long b) {
    if (a == 0 || b == 0) {
        return 0;
    }
    return a / gcd(a, b) * b;
}

Беззнаковая версия НОД - алгоритм Евклида для целых чисел. Возвращает натуральное число, если среди аргументов есть не нули. Если оба нуля, возвращает ноль.

unsigned long long gcd(unsigned long long a, unsigned long long b) {
    while (b != 0) {
        const auto c = a % b;
        a = b;
        b = c;
    }
    return a;
}

Для полноты я добавил знаковую версию НОД в полную программу:

#include <iostream>

unsigned long long gcd(unsigned long long a, unsigned long long b) {
    while (b != 0) {
        const auto c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long long gcd(long long a, long long b) {
    return static_cast<long long>(gcd(
        static_cast<unsigned long long>(std::abs(a)),
        static_cast<unsigned long long>(std::abs(b))
    ));
}

unsigned long long lcm(unsigned long long a, unsigned long long b) {
    if (a == 0 || b == 0) {
        return 0;
    }
    return a / gcd(a, b) * b;
}

long long lcm(long long a, long long b) {
    return static_cast<long long>(lcm(
        static_cast<unsigned long long>(std::abs(a)),
        static_cast<unsigned long long>(std::abs(b))
    ));
}

int main() {
    long long a;
    long long b;
    if (!(std::cin >> a >> b)) {
        std::exit(1);
    }
    std::cout << gcd(a, b) << ' ' << lcm(a, b) << '\n';
}

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror gcd-lcm.cpp

$ echo -15 21 | ./a.out 
3 105

$ echo -15 -21 | ./a.out 
3 105

$ echo 15 -21 | ./a.out 
3 105

$ echo 15 21 | ./a.out 
3 105

БЛОГ НА HUSL

Слишком долго ищет НОК больших чисел

Ответы (2 шт):