O Teorema Chinês do Resto (TCR) é um pilar da teoria dos números que fornece um método para resolver sistemas de congruências lineares. Ele permite a descoberta de um número inteiro que satisfaz múltiplas condições de resto simultaneamente, sob a condição de que os módulos de cada congruência sejam coprimos entre si.

Teorema Chinês do Resto (TCR)

Considere um sistema de congruências na seguinte forma:

\[ x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \] Aqui, \(m_1, m_2, \ldots, m_n\) são inteiros positivos que são pairwise coprimos (ou seja, \(\gcd(m_i, m_j) = 1\) para quaisquer \(i \neq j\)).

Para obter a solução, definimos as seguintes grandezas:

• \(M = \prod_{i=1}^{n} m_i\): o produto de todos os módulos.
• \(M_i = \frac{M}{m_i}\): o produto de todos os módulos, excluindo \(m_i\).
• \(t_i = M_i^{-1} \pmod{m_i}\): o inverso multiplicativo de \(M_i\) módulo \(m_i\). Este inverso é garantido por existir devido à propriedade de coprimalidade de \(M_i\) e \(m_i\).

Uma solução particular \(x_0\) para este sistema é dada pela soma:

\[ x_0 = \sum_{i=1}^{n} a_i t_i M_i \] A menor solução inteira positiva é então \(x = x_0 \pmod M\).

Demonstração da Solução

Para validar que \(x_0 = \sum_{i=1}^{n} a_i t_i M_i\) constitui uma solução, devemos verificar que \(x_0 \equiv a_j \pmod{m_j}\) para cada \(j \in \{1, \ldots, n\}\).

Consideremos a \(j\)-ésima congruência, \(x \equiv a_j \pmod{m_j}\). Ao avaliarmos \(x_0\) módulo \(m_j\), temos:

\[ x_0 \pmod{m_j} = \left( \sum_{i=1}^{n} a_i t_i M_i \right) \pmod{m_j} \] Para qualquer termo \(a_i t_i M_i\) onde \(i \neq j\), o módulo \(m_j\) é um fator de \(M_i\). Isso ocorre porque \(M_i\) é o produto de todos os \(m_k\) exceto \(m_i\), e \(m_j\) é um desses fatores. Consequentemente, \(M_i \equiv 0 \pmod{m_j}\) quando \(i \neq j\).

Isso simplifica a expressão da soma para:

\[ x_0 \pmod{m_j} = (a_j t_j M_j) \pmod{m_j} \] Pela nossa definição, \(t_j M_j \equiv 1 \pmod{m_j}\). Substituindo esta equivalência na expressão, obtemos:

\[ x_0 \pmod{m_j} = (a_j \cdot 1) \pmod{m_j} \\ x_0 \equiv a_j \pmod{m_j} \] Esta prova confirma que \(x_0\) satisfaz cada congruência do sistema. A forma geral da solução é \(x = x_0 + kM\), para qualquer inteiro \(k\). Portanto, a menor solução positiva é \(x_0 \pmod M\).

Código para o TCR

A implementação prática do TCR exige o cálculo do inverso multiplicativo modular, geralmente realizado através do Algoritmo Estendido de Euclides. A função extended_gcd(a, b, x, y) retorna \(\gcd(a, b)\) e determina \(x, y\) que satisfazem a identidade de Bézout, \(ax + by = \gcd(a, b)\). Se \(\gcd(a, m) = 1\), então \(ax + my = 1\), implicando que \(x\) é o inverso mlutiplicativo de \(a\) módulo \(m\).

#include <iostream>
#include <vector>
#include <numeric> // Para std::gcd no C++17, se aplicável
#include <cstdio>  // Para getchar/putchar para I/O rápida

// Usamos long long para módulos e resultados que podem ser grandes.
typedef long long ll;

// Funções de I/O personalizadas para melhorar o desempenho em ambientes competitivos.
inline ll ler_long_long() {
    ll valor = 0;
    bool negativo = false;
    int caractere = getchar();
    while (caractere < '0' || caractere > '9') {
        if (caractere == '-') negativo = true;
        caractere = getchar();
    }
    while (caractere >= '0' && caractere <= '9') {
        valor = valor * 10 + (caractere - '0');
        caractere = getchar();
    }
    return negativo ? -valor : valor;
}

inline void imprimir_long_long(ll valor, bool nova_linha) {
    if (valor < 0) {
        putchar('-');
        valor = -valor;
    }
    if (valor == 0) {
        putchar('0');
    } else {
        char buffer[40]; // Suficiente para armazenar dígitos de um long long
        int indice = 0;
        while (valor > 0) {
            buffer[indice++] = (valor % 10) + '0';
            valor /= 10;
        }
        while (indice > 0) {
            putchar(buffer[--indice]);
        }
    }
    if (nova_linha) putchar('\n');
}

// Algoritmo Estendido de Euclides: calcula gcd(a, b) e encontra x, y para ax + by = gcd(a, b)
ll extended_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll gcd_calculado = extended_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return gcd_calculado;
}

int main() {
    int num_equacoes = ler_long_long();
    
    std::vector<ll> restos(num_equacoes);  // a_i
    std::vector<ll> modulos(num_equacoes); // m_i

    // Leitura das congruências
    for (int i = 0; i < num_equacoes; ++i) {
        modulos[i] = ler_long_long();
        restos[i] = ler_long_long();
    }

    ll produto_total_M = 1; // M = m1 * m2 * ... * mn
    for (int i = 0; i < num_equacoes; ++i) {
        produto_total_M *= modulos[i];
    }

    ll solucao_x_0 = 0;
    for (int i = 0; i < num_equacoes; ++i) {
        ll modulo_atual = modulos[i];
        ll resto_atual = restos[i];

        // Mi = M / mi
        ll produto_Mi_dividido_por_mi = produto_total_M / modulo_atual;

        ll x_bezout, y_bezout;
        // Calcula o inverso multiplicativo de Mi mod mi: (Mi * t_i) % mi = 1
        extended_gcd(produto_Mi_dividido_por_mi, modulo_atual, x_bezout, y_bezout);
        
        // Garante que t_i (x_bezout) seja positivo e no intervalo [0, modulo_atual - 1]
        ll inverso_multiplicativo_ti = (x_bezout % modulo_atual + modulo_atual) % modulo_atual;

        // Contribuição do termo atual para a solução total: (a_i * t_i * M_i)
        // É importante modular cada fator e a soma para evitar overflows intermediários,
        // embora o 'long long' seja bastante grande. Se M fosse muito grande, seria necessário __int128.
        ll termo_contribuicao = (resto_atual * inverso_multiplicativo_ti % produto_total_M * produto_Mi_dividido_por_mi % produto_total_M + produto_total_M) % produto_total_M;
        solucao_x_0 = (solucao_x_0 + termo_contribuicao) % produto_total_M;
    }

    imprimir_long_long(solucao_x_0, true);

    return 0;
}
</ll></ll>

Teorema Chinês do Resto Estendido (TCRE)

O Teorema Chinês do Resto Estendido (TCRE) trata do mesmo problema de encontrar um número \(x\) que satisfaça um sistema de congruências, mas sem a restrição de que os módulos \(m_i\) precisam ser coprimos entre si. A abordagem do TCRE difere fundamentalmente da do TCR, focando na combinação sequencial de congruências em pares.

Processo de Combinação de Congruências

Consideremos a fusão de duas congruências arbitrárias de um sistema:

\[ x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \] Da primeira congruência, podemos expressar \(x\) como \(x = a_1 + k_1 m_1\), onde \(k_1\) é um número inteiro. Substituindo esta expressão na segunda congruência, obtemos:

\[ a_1 + k_1 m_1 \equiv a_2 \pmod{m_2} \\ k_1 m_1 \equiv a_2 - a_1 \pmod{m_2} \] Esta é uma congruência linear para a variável \(k_1\), que pode ser reescrita como uma equação Diofantina:

\[ k_1 m_1 - k_2 m_2 = a_2 - a_1 \] Para que esta equação tenha soluções para \(k_1\) e \(k_2\), é uma condição necessária que \(\gcd(m_1, m_2)\) divida \((a_2 - a_1)\). Caso esta condição não seja atendida, o sistema não possui solução, e podemos concluir imediatamente a inexistência de uma solução global para o sistema original.

Assumidno que \(\gcd(m_1, m_2)\) divide \((a_2 - a_1)\), empregamos o Algoritmo Estendido de Euclides para determinar uma solução particular para \(k_1\). Seja \(d = \gcd(m_1, m_2)\). Dividindo a equação Diofantina por \(d\):

\[ k_1 \frac{m_1}{d} - k_2 \frac{m_2}{d} = \frac{a_2 - a_1}{d} \] Ao aplicar o Algoritmo Estendido de Euclides a \(\frac{m_1}{d}\) e \(\frac{m_2}{d}\), podemos encontrar \(x', y'\) tais que \(x' \frac{m_1}{d} + y' \frac{m_2}{d} = \gcd(\frac{m_1}{d}, \frac{m_2}{d}) = 1\). É importante notar que os coeficientes \(\frac{m_1}{d}\) e \(\frac{m_2}{d}\) são coprimos. Multiplicando esta identidade por \(\frac{a_2-a_1}{d}\), obtemos uma solução particular para \(k_1\):

\[ k_1 = x' \frac{a_2 - a_1}{d} \pmod{\frac{m_2}{d}} \] Com \(k_1\) determinado, a solução geral para \(k_1\) é \(k_1 = k_{1,0} + k \frac{m_2}{d}\), onde \(k_{1,0}\) é a solução particular encontrada e \(k\) é um inteiro. Substituindo este valor de \(k_1\) de volta na expressão para \(x\):

\[ x = a_1 + (k_{1,0} + k \frac{m_2}{d}) m_1 \\ x = a_1 + k_{1,0} m_1 + k \frac{m_1 m_2}{d} \] Isto implica que a solução combinada das duas congruências assume a forma:

\[ x \equiv (a_1 + k_{1,0} m_1) \pmod{\frac{m_1 m_2}{d}} \] O novo resto é \(a' = a_1 + k_{1,0} m_1\), e o novo módulo é \(m' = \frac{m_1 m_2}{d} = \operatorname{lcm}(m_1, m_2)\). Dessa forma, o prbolema é simplificado para um novo sistema com uma congruência a menos. Este processo é iterado até que todas as congruências sejam combinadas em uma única.

Durante a implementação, é vital garantir que os restos e módulos permaneçam dentro de intervalos positivos e válidos após cada etapa de combinação, aplicando a operação de módulo para normalizar os resultados.

Código para o TCRE

#include <iostream>
#include <cstdio> // Para getchar/putchar para I/O rápida

// Usamos __int128 para lidar com módulos e produtos intermediários que podem
// facilmente exceder os limites de um 'long long', pois os módulos não são coprimos.
typedef __int128 int128_t;

// Funções de I/O personalizadas para int128_t
inline int128_t ler_int128() {
    int128_t valor = 0;
    bool negativo = false;
    int caractere = getchar();
    while (caractere < '0' || caractere > '9') {
        if (caractere == '-') negativo = true;
        caractere = getchar();
    }
    while (caractere >= '0' && caractere <= '9') {
        valor = valor * 10 + (caractere - '0');
        caractere = getchar();
    }
    return negativo ? -valor : valor;
}

inline void imprimir_int128(int128_t valor, bool nova_linha) {
    if (valor < 0) {
        putchar('-');
        valor = -valor;
    }
    if (valor == 0) {
        putchar('0');
    } else {
        char buffer[60]; // Suficiente para um __int128 (até 39 dígitos)
        int indice = 0;
        while (valor > 0) {
            buffer[indice++] = (valor % 10) + '0';
            valor /= 10;
        }
        while (indice > 0) {
            putchar(buffer[--indice]);
        }
    }
    if (nova_linha) putchar('\n');
}

// Algoritmo Estendido de Euclides para int128_t
int128_t extended_gcd(int128_t a, int128_t b, int128_t &x, int128_t &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int128_t gcd_val = extended_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return gcd_val;
}

// Função para combinar duas congruências:
// x = resto_atual (mod modulo_atual)
// x = proximo_resto    (mod proximo_modulo)
// Retorna true se a combinação for bem-sucedida, false se não houver solução.
// resto_atual e modulo_atual são atualizados com o resultado da combinação.
bool combinar_congruencias(int128_t &resto_atual, int128_t &modulo_atual,
                         int128_t proximo_resto, int128_t proximo_modulo) {
    
    int128_t x_gcd, y_gcd;
    int128_t valor_gcd = extended_gcd(modulo_atual, proximo_modulo, x_gcd, y_gcd);
    
    // Calculamos a diferença (a_2 - a_1)
    int128_t diferenca_restos = proximo_resto - resto_atual;

    // Se (a_2 - a_1) não for divisível por gcd(m_1, m_2), não há solução
    if (diferenca_restos % valor_gcd != 0) {
        return false;
    }

    // Calcula uma solução particular para k_1 em k_1 * m_1 = (a_2 - a_1) (mod m_2)
    // k_1 = ((diferenca_restos / valor_gcd) * x_gcd) % (proximo_modulo / valor_gcd)
    int128_t fator_k1 = diferenca_restos / valor_gcd;
    int128_t modulo_para_k1 = proximo_modulo / valor_gcd;
    
    // Assegura que x_gcd (o coeficiente de m_1 na identidade de Bezout) seja positivo
    x_gcd = (x_gcd % modulo_para_k1 + modulo_para_k1) % modulo_para_k1;
    
    int128_t solucao_k1 = (fator_k1 * x_gcd) % modulo_para_k1;

    // A nova congruência resultante é:
    // x = (resto_atual + solucao_k1 * modulo_atual) (mod lcm(modulo_atual, proximo_modulo))
    // lcm(m1, m2) = (m1 * m2) / gcd(m1, m2)
    int128_t novo_modulo_combinado = (modulo_atual / valor_gcd) * proximo_modulo;
    int128_t novo_resto_combinado = (resto_atual + solucao_k1 * modulo_atual) % novo_modulo_combinado;
    
    // Normaliza o resto para ser não negativo
    novo_resto_combinado = (novo_resto_combinado + novo_modulo_combinado) % novo_modulo_combinado;

    // Atualiza os valores para a próxima iteração
    resto_atual = novo_resto_combinado;
    modulo_atual = novo_modulo_combinado;

    return true;
}

int main() {
    int num_equacoes = ler_int128();
    
    int128_t valor_a_atual = ler_int128();
    int128_t valor_m_atual = ler_int128();

    // Processa as congruências restantes uma a uma
    for (int i = 1; i < num_equacoes; ++i) {
        int128_t proximo_valor_a = ler_int128();
        int128_t proximo_valor_m = ler_int128();
        
        // Tenta combinar a congruência acumulada (valor_a_atual, valor_m_atual)
        // com a próxima (proximo_valor_a, proximo_valor_m)
        if (!combinar_congruencias(valor_a_atual, valor_m_atual, proximo_valor_a, proximo_valor_m)) {
            imprimir_int128(-1, true); // Retorna -1 se não houver solução
            return 0;
        }
    }
    
    // A solução final é o resto acumulado módulo o módulo acumulado
    imprimir_int128(valor_a_atual, true);

    return 0;
}