P3811: Inverso Modular Recursivo

Para resolver o problema com complexidade O(n), utilizamos uma fórmula recursiva. Defina t = p div i e k = p mod i. A partir de t * i + k ≡ 0 (mod p), deduz-se k ≡ -t * i (mod p), resultando em inv[i] ≡ -t * inv[k] (mod p). Simplificando, inv[i] ≡ -(p div i) * inv[p mod i] (mod p). Para evitar valores negativos, adicione p ao resultado.

#include <iostream>
using namespace std;
const int MAX_SIZE = 1000010;
long long inv_arr[MAX_SIZE];

void compute_inverses(int n, int modulus) {
    inv_arr[1] = 1;
    for (int idx = 2; idx <= n; ++idx) {
        int divisor = modulus / idx;
        int remainder = modulus % idx;
        inv_arr[idx] = (modulus - divisor * inv_arr[remainder]) % modulus;
        if (inv_arr[idx] < 0) inv_arr[idx] += modulus;
    }
}

int main() {
    int n, p;
    cin >> n >> p;
    compute_inverses(n, p);
    for (int i = 1; i <= n; ++i) {
        cout << inv_arr[i] << "\n";
    }
    return 0;
}

P1349: Sequência de Fibonacci Generalizada com Exponenciação Matricial

Este problema envolve a sequência de Fibonacci generalizada, onde os termos são definidos por A1, A2 e recorrência An = p*An-1 + q*An-2. Para calcular o n-ésimo termo eficeintemente, usamos exponenciação matricial. A matriz de tarnsformação é construída e elevada à potência n-2 para obter o resultado.

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

struct Matrix {
    ll data[2][2];
    Matrix() { memset(data, 0, sizeof(data)); }
};

Matrix multiply(const Matrix &a, const Matrix &b, ll mod) {
    Matrix res;
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                res.data[i][j] = (res.data[i][j] + a.data[i][k] * b.data[k][j]) % mod;
    return res;
}

Matrix matrix_power(Matrix base, ll exponent, ll mod) {
    Matrix result;
    result.data[0][0] = result.data[1][1] = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1)
            result = multiply(result, base, mod);
        base = multiply(base, base, mod);
        exponent /= 2;
    }
    return result;
}

int main() {
    ll p, q, a1, a2, n, mod;
    cin >> p >> q >> a1 >> a2 >> n >> mod;
    if (n == 1) {
        cout << a1 % mod << "\n";
        return 0;
    }
    if (n == 2) {
        cout << a2 % mod << "\n";
        return 0;
    }
    Matrix trans;
    trans.data[0][0] = p;
    trans.data[0][1] = 1;
    trans.data[1][0] = q;
    trans.data[1][1] = 0;
    trans = matrix_power(trans, n - 2, mod);
    ll result = (trans.data[0][0] * a2 + trans.data[0][1] * a1) % mod;
    cout << result << "\n";
    return 0;
}

P2421: Encontro em Ilha Deserta via Algoritmo de Euclides Estendido

Dado o problema de determinar o módulo M mínimo para evitar encontros entre n pessoas, onde a posição de cada pessoa é Ci + x*Pi mod M. Para dois indivíduos i e j, a condição de ancontro é Ci + x*Pi ≡ Cj + x*Pj (mod M), que pode ser reescrita como x*(Pi - Pj) ≡ Cj - Ci (mod M). Isso leva à equação diofantina x*(Pi - Pj) - M*y = Cj - Ci. Usamos o algoritmo de Euclides estendido para verificar soluções e validá-las contra os limites de sobrevivência.

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int gcd_val = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd_val;
}

bool check_valid(int M, int n, int C[], int P[], int L[]) {
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int a = P[i] - P[j];
            int b = M;
            int c = C[j] - C[i];
            int x, y;
            int g = extended_gcd(a, b, x, y);
            if (c % g != 0) continue;
            int b_reduced = b / g;
            x = (x * (c / g)) % b_reduced;
            if (x < 0) x += b_reduced;
            if (x <= L[i] && x <= L[j]) return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    int C[20], P[20], L[20];
    int max_c = 0;
    for (int i = 0; i < n; ++i) {
        cin >> C[i] >> P[i] >> L[i];
        max_c = max(max_c, C[i]);
    }
    for (int M = max_c; ; ++M) {
        if (check_valid(M, n, C, P, L)) {
            cout << M << "\n";
            break;
        }
    }
    return 0;
}

P3868: Resolução de Congruências usando Teorema do Resto Chinês

O problema envolve encontrar um número n tal que b_i divide (n - a_i) para cada i, o que equivale a n ≡ a_i (mod b_i). Aplicamos o Teorema do Resto Chinês (CRT) para resolver o sistema de congruências, assumindo que os módulos b_i são coprimos.

#include <iostream>
using namespace std;
typedef long long ll;

ll extended_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll gcd_val = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd_val;
}

ll modular_multiply(ll a, ll b, ll mod) {
    ll result = 0;
    a %= mod;
    while (b > 0) {
        if (b % 2 == 1) result = (result + a) % mod;
        a = (a * 2) % mod;
        b /= 2;
    }
    return result;
}

ll crt(int n, ll a[], ll b[]) {
    ll M = 1;
    for (int i = 0; i < n; ++i) M *= b[i];
    ll solution = 0;
    for (int i = 0; i < n; ++i) {
        ll Mi = M / b[i];
        ll inv, y;
        extended_gcd(Mi, b[i], inv, y);
        inv = (inv % b[i] + b[i]) % b[i];
        ll term = modular_multiply(modular_multiply(Mi, inv, M), a[i], M);
        solution = (solution + term) % M;
    }
    return solution;
}

int main() {
    int n;
    cin >> n;
    ll a[100], b[100];
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    for (int i = 0; i < n; ++i) a[i] = (a[i] % b[i] + b[i]) % b[i];
    ll ans = crt(n, a, b);
    cout << ans << "\n";
    return 0;
}