cálculo de Máximo Divisor Comum (MDC) e Mínimo Múltiplo Comum (MMC)

// Fatoração e Cálculo de Máximo Divisor Comum (MDC) e Mínimo Múltiplo Comum (MMC)
// VERSÕES: 0.1: 18/04/2026: versão testada com sucesso com vários valores
//          0.2: 19/04/2026: otimizações de todos os tipos, envolvendo CharGPT,
//                           principalmente passando de array para vector, nisso excluindo Ultimo e Maximo
//          0.3: 20/04/2026: retirada a necessidade de avaliar raiz de produto, tirado getExpemte() Primo e math.h
//                           argumentos para número de testes, melhorias pelo ChatGPT

// ATENÇÃO
// embora os tempos fiquem melhores com a opção de otimização -O3 ao compilar,
// ela não faz as chamadas a setProduto(), mdc() e mmc() dentro das medições
// de tempo, o que causa valores próximos ou iguais a zero
// ATUALIZAÇÃO
// volatile int64_t mdc, mmc, qtdeFatores parece ter resolvido o problema de compilar com -O3

#include <cstdint>  // int64_t
#include <iostream> // cout, endl
#include <cstdlib>  // calloc, free
#include <algorithm>  // min, max
#include <chrono>  // now(), time_point, milisecond
#include <vector>  // vetores

using namespace std;

// função de expomnencial de inteiros (para uso no domínio do problema, base >= 0, expoente >= 0)
int64_t powint(int64_t base, int64_t exp) {
    int64_t r = 1;
    while (exp > 0) {
        if (exp & 1) r *= base;
        base *= base;
        exp >>= 1;
    }
    return r;
}

// #include <cstdint>
// #include <cstdlib>

// using namespace std;

// using u64 = uint64_t;
// using u128 = __uint128_t;

// // ------------------------------
// // MDC (algoritmo de Euclides)
// // ------------------------------
// u64 mdc(u64 a, u64 b) {
//     while (b != 0) {
//         u64 r = a % b;
//         a = b;
//         b = r;
//     }
//     return a;
// }

// // ------------------------------
// // MMC seguro (evita overflow intermediário)
// // ------------------------------
// u64 mmc(u64 a, u64 b) {
//     u64 g = mdc(a, b);
//     // (a / g) * b evita overflow mais cedo
//     return (u128)(a / g) * b;
// }

// classe que encontra os fatores de um Produto e com as funções estáticas mdc e mmc
class Fatoracao{
    private:
        int64_t Produto;
        vector<std::pair<int64_t, int64_t>> VExpoentes;
    public:
        Fatoracao(int64_t produto);
        Fatoracao(void);
        bool setProduto(int64_t produto);
        inline int64_t getProduto(void) const ;
        inline bool getPrimo(void) const ;
        inline size_t getQuantidadeFatores() const ;
        inline int64_t getFatorPorIndice(size_t i) const ;
        inline int64_t getExpoentePorIndice(size_t i) const ;
        static int64_t mdc(const Fatoracao& num1, const Fatoracao& num2);
        static int64_t mmc(const Fatoracao& num1, const Fatoracao& num2);
        Fatoracao(const Fatoracao&) = delete;
        Fatoracao& operator=(const Fatoracao&) = delete;
};

// muda o valor do produto, preenche os atributos, principalmente VExpoentes, que são fatores indexados
// caso retorne false, não usar o objeto, pois irá se comportar como se tivesse o valor 1
bool Fatoracao::setProduto(int64_t produto) {
    Produto = produto;

    // limpa VExpoentes para poder reutilizar o mesmo objeto para várias fatorações
    VExpoentes.clear();

    // se produto == 1, não preenche VExpoentes
    // se produto < 1, equivalente a 1, com a diferença que setProduto retorna falso (erro)
    if(produto < 2) {
        return produto == 1;
    }

    // encontra e guarda os expoentes para os números em VExpoentes
    int64_t indice = 3, atual = 0;

    // primeiro, o fator 2
    while(produto % 2 == 0) {
        if(atual == 2) VExpoentes.back().second++;
        else { VExpoentes.push_back({2, 1}); atual = 2; }

        produto /= 2;
    }

    // depois, os fatores ímpares
    while(indice * indice <= produto) {
        if(produto % indice == 0) {
            if(indice == atual) VExpoentes.back().second++;
            else { VExpoentes.push_back({indice, 1}); atual = indice; }

            produto /= indice;
        } else {
            indice += 2;
        }
    }

    // o produto que sobra
    if(produto > 1) { if(produto == atual) VExpoentes.back().second++;
                      else VExpoentes.push_back({produto, 1}); }

    return true;
}

// retorna o número fatorado original, inválido se setProduto retornou false
inline int64_t Fatoracao::getProduto(void) const { return Produto; }

// retorna a quantidade de fatores
inline size_t Fatoracao::getQuantidadeFatores() const { return VExpoentes.size(); }

// retorna qual é o fator do elemento indice do vetor de fatores
inline int64_t Fatoracao::getFatorPorIndice(size_t indice) const { return (indice < VExpoentes.size()) ? VExpoentes[indice].first : 0; }

// retorna qual é o expoente do elemento indice do vetor de fatores
inline int64_t Fatoracao::getExpoentePorIndice(size_t indice) const { return (indice < VExpoentes.size()) ? VExpoentes[indice].second : 0; }

// retorna o Máximo Divisor Comum (MDC) entre dois números fatorados
int64_t Fatoracao::mdc(const Fatoracao& num1, const Fatoracao& num2) {
    int64_t produto = 1, indice1 = 0, indice2 = 0, multiplicador;
    size_t qtdFatores1 = num1.getQuantidadeFatores(); size_t qtdFatores2 = num2.getQuantidadeFatores();
    int64_t fator1 = num1.getFatorPorIndice(0); int64_t fator2 = num2.getFatorPorIndice(0);

    while(true) {
        if(indice1 == qtdFatores1 || indice2 == qtdFatores2) break;

        if(fator2 > fator1) {
            indice1++;
            if(indice1 < qtdFatores1) fator1 = num1.getFatorPorIndice(indice1);
            continue;
        }

        if(fator1 > fator2) {
            indice2++;
            if(indice2 < qtdFatores2) fator2 = num2.getFatorPorIndice(indice2);
            continue;
        }

        multiplicador = powint(fator1, min(num1.getExpoentePorIndice(indice1), num2.getExpoentePorIndice(indice2)));
        if(produto > INT64_MAX / multiplicador) return 0;
        produto *= multiplicador;

        indice1++;
        if(indice1 < qtdFatores1) fator1 = num1.getFatorPorIndice(indice1);
        indice2++;
        if(indice2 < qtdFatores2) fator2 = num2.getFatorPorIndice(indice2);
    }
    return produto;
}

// retorna o Mínimo Múltiplo Comum (MMC) entre dois números fatorados
int64_t Fatoracao::mmc(const Fatoracao& num1, const Fatoracao& num2) {
    int64_t produto = 1, indice1 = 0, indice2 = 0, multiplicador;
    size_t qtdFatores1 = num1.getQuantidadeFatores(); size_t qtdFatores2 = num2.getQuantidadeFatores();
    int64_t fator1 = num1.getFatorPorIndice(0); int64_t fator2 = num2.getFatorPorIndice(0);

    while(true) {
        if(indice1 == qtdFatores1 && indice2 == qtdFatores2) break;

        if(indice1 < qtdFatores1 && (indice2 == qtdFatores2 || fator2 > fator1)) {
            multiplicador = powint(fator1, num1.getExpoentePorIndice(indice1));
            if(produto > INT64_MAX / multiplicador) return 0;
            produto *= multiplicador;

            indice1++;
            if(indice1 < qtdFatores1) fator1 = num1.getFatorPorIndice(indice1);
            continue;
        }

        if(indice2 < qtdFatores2 && (indice1 == qtdFatores1 || fator1 > fator2)) {
            multiplicador = powint(fator2, num2.getExpoentePorIndice(indice2));
            if(produto > INT64_MAX / multiplicador) return 0;
            produto *= multiplicador;

            indice2++;
            if(indice2 < qtdFatores2) fator2 = num2.getFatorPorIndice(indice2);
            continue;
        }

        multiplicador = powint(fator1,max(num1.getExpoentePorIndice(indice1), num2.getExpoentePorIndice(indice2)));
        if(produto > INT64_MAX / multiplicador) return 0;
        produto *= multiplicador;

        indice1++;
        if(indice1 < qtdFatores1) fator1 = num1.getFatorPorIndice(indice1);
        indice2++;
        if(indice2 < qtdFatores2) fator2 = num2.getFatorPorIndice(indice2);
    }
    return produto;
}

// construtor que recebe um valor para o produto fatorado e delega o fatoramento para SetProduto()
Fatoracao::Fatoracao(int64_t produto) {
    setProduto(produto);
}

// construtor que não recebe valor para o produto fatorado e preenche os atributos com valores zerados
Fatoracao::Fatoracao(void) {
    Produto = 0;
}

// imprime os fatores de um produto num1, de número numero
void imprimeFatores(const Fatoracao& fat, int numero) {
    // imprime o fatoramento do número
    cout << endl << "NÚMERO " << numero << ":" << endl;

    size_t quantidade = fat.getQuantidadeFatores();
    for(size_t indice = 0; indice < quantidade; indice++)
        cout << "Fator " << fat.getFatorPorIndice(indice) << " vezes " << fat.getExpoentePorIndice(indice) << endl;
}

// testes
int main(int argc, char* argv[]) {
    Fatoracao num1, num2; long xFatorar = 1000, xMdcMmc = 1000;
    int64_t val1, val2; volatile int64_t mdc, mmc, qtdeFatores = 0;

    chrono::steady_clock::time_point inicio, fim;
    chrono::milliseconds duracao;

    if(argc > 1) xFatorar = strtol(argv[1], nullptr, 10);
    if(argc > 2) xMdcMmc = strtol(argv[2], nullptr, 10);

    while(true) {

        // pede o primeiro número, validando usando setProduto como avaliador de sucesso
        while(true) {
            cout << "Número 1: ";
            cin >> val1;
            if(val1 == 0) exit(0);
            if(num1.setProduto(val1)) break;
            cout << "Número muito pequeno ou muito grande!" << endl;
        }


        // pede o segundo número, validando usando setProduto como avaliador de sucesso
        while(true) {
            cout << "Número 2: ";
            cin >> val2;
            if(val2 == 0) exit (0);
            if(num2.setProduto(val2)) break;
            cout << "Número muito pequeno ou muito grande!" << endl;
        }


        // imprime os fatoramentos dos números
        imprimeFatores(num1, 1);
        imprimeFatores(num2, 2);

        cout << endl;


        // imprime o Máximo Divisor Comum (MDC)
        mdc = Fatoracao::mdc(num1, num2);
        cout << "MDC = " << mdc << endl;

        // imprime o Mínimo Múltiplo Comum (MMC)
        mmc = Fatoracao::mmc(num1, num2);
        cout << "MMC = " << mmc << endl << endl;


        // mede o tempo de fatorar num1 e num2 1000 vezes
        inicio = chrono::steady_clock::now();
        for(long indice = 0; indice < xFatorar; indice++) {
            num1.setProduto(val1);
            num2.setProduto(val2);
            qtdeFatores += num1.getQuantidadeFatores() + num2.getQuantidadeFatores();
        }
        fim = chrono::steady_clock::now();

        duracao = chrono::duration_cast<chrono::milliseconds>(fim - inicio);
        cout << "Tempo decorrido fatoração (num1, num2) (" << xFatorar << " vezes): " << duracao.count() << " ms" << endl << endl;


        // mede o tempo de calcular MDC + MMC 1000 vezes
        inicio = chrono::steady_clock::now();
        for(long indice = 0; indice < xMdcMmc; indice++) {
            mdc = Fatoracao::mdc(num1, num2);
            mmc = Fatoracao::mmc(num1, num2);
        }
        fim = chrono::steady_clock::now();

        duracao = chrono::duration_cast<chrono::milliseconds>(fim - inicio);
        cout << "Tempo decorrido MDC + MMC (" << xMdcMmc << " vezes): " << duracao.count() << " ms" << endl << endl;
    }
}