Este artigo aborda a aplicação de métodos de peneira de primos, como a Peneira de Eratóstenes e peneira linear, para resolver problemas de teoria dos números em competições de programação. A partir de um problema específico do Codeforces (Problem D), são apresentadas soluções que utilizam algoritmos de peneira para calcular divisores comuns, subsequências coprimas e pareamentos eficientes.

Implementação da Peneira de Primos

A peneira de Eratóstenes é otimizada para gerar primos até um limite dado, armazenando-os em um array e marcando números compostos. A seguir, um exemplo em C++ adaptado:

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

constexpr int MAX_N = 300010, MOD_VAL = 1000000007;
const int UPPER = 15000002;
int array_vals[MAX_N], freq[UPPER];
int prime_list[UPPER / 10];
bool composite[UPPER];
int n_items;

void generate_primes(int limit) {
    composite[1] = true;
    for (int idx = 2; idx <= limit; idx++) {
        if (!composite[idx]) prime_list[++prime_list[0]] = idx;
        for (int k = 1; idx * prime_list[k] < limit; k++) {
            composite[idx * prime_list[k]] = true;
            if (idx % prime_list[k] == 0) break;
        }
    }
}

No contexto do problema, é necessário encontrar o maior conjunto de elementos que compartilham um divisor comum. O código prinicpal calcula o máximo divisor comum (MDC) de todos os elementos e, em seguida, utiliza a peneira para analisar frequências de divisores.

void solve() {
    cin >> n_items;
    int common_div = 0;
    for (int i = 1; i <= n_items; i++) {
        cin >> array_vals[i];
        common_div = __gcd(common_div, array_vals[i]);
    }
    int max_val = 0;
    for (int i = 1; i <= n_items; i++) {
        array_vals[i] /= common_div;
        max_val = max(max_val, array_vals[i]);
        freq[array_vals[i]]++;
    }
    generate_primes(max_val);
    int best_count = 0;
    for (int i = 1; i <= prime_list[0]; i++) {
        int cnt = 0;
        for (int j = prime_list[i]; j <= max_val; j += prime_list[i])
            cnt += freq[j];
        if (cnt > 0) best_count = max(best_count, cnt);
    }
    cout << (best_count == 0 ? -1 : n_items - best_count) << endl;
}

Solução para Subsequências Coprimas (Problema 803F)

O problema envolve contar subsequências onde todos os elementos são coprimos entre si. Utiliza-se o princípio de inclusão-exclusão com a peneira para somar sobre múltiplos. A implementação abaixo emprega uma abordagem bottom-up para calcular as contagens.

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int MOD = 1000000007;
const int SIZE = 100010;
long long values[SIZE], result[SIZE], cnt_div[SIZE];
long long pow2[SIZE];
int n_data;

void solve() {
    cin >> n_data;
    pow2[0] = 1;
    int max_num = 0;
    for (int i = 1; i <= n_data; i++) {
        cin >> values[i];
        cnt_div[values[i]]++;
        pow2[i] = (pow2[i - 1] << 1) % MOD;
        max_num = max(max_num, values[i]);
    }
    for (int i = 1; i <= max_num; i++)
        for (int j = i * 2; j <= max_num; j += i)
            cnt_div[i] += cnt_div[j];
    for (int i = max_num; i > 0; i--) {
        result[i] = pow2[cnt_div[i]] - 1;
        for (int j = 2 * i; j <= max_num; j += i) {
            result[i] -= result[j];
            if (result[i] < 0) result[i] += MOD;
        }
    }
    cout << result[1] << endl;
}

Pareamento de Números (Problema 449C)

Este problema requer formar pares de números que compartilham um fator primo, maximizando o número de pares. A solução usa uma peneira linear para gerar primos e, em seguida, agrupa números por divisores primos para formar pares.

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int MAX = 100010;
int n_val;
int primes[MAX];
bool used[MAX];

void sieve_linear() {
    used[1] = true;
    for (int i = 2; i < MAX; i++) {
        if (!used[i]) primes[++primes[0]] = i;
        for (int j = 1; j <= primes[0] && primes[j] * i < MAX; j++) {
            used[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

void solve() {
    cin >> n_val;
    sieve_linear();
    vector<pair<int, int>> pairs_list;
    memset(used, false, sizeof used);
    for (int i = primes[0]; i > 0; i--) {
        vector<int> multiples;
        for (int j = primes[i]; j <= n_val; j += primes[i])
            if (!used[j]) multiples.push_back(j);
        int len = multiples.size();
        if (len <= 1) continue;
        if (len % 2 == 1) {
            pairs_list.push_back({multiples[0], multiples[len - 1]});
            used[multiples[0]] = used[multiples[len - 1]] = true;
            for (int k = 2; k < len - 1; k += 2) {
                pairs_list.push_back({multiples[k], multiples[k + 1]});
                used[multiples[k]] = used[multiples[k + 1]] = true;
            }
        } else {
            for (int k = 0; k < len; k += 2) {
                pairs_list.push_back({multiples[k], multiples[k + 1]});
                used[multiples[k]] = used[multiples[k + 1]] = true;
            }
        }
    }
    cout << pairs_list.size() << endl;
    for (auto &[x, y] : pairs_list) cout << x << " " << y << endl;
}

Contagem de Pares com GCD Específico (Problema D)

Aqui, o objetivo é contar pares de números cujo MDC é exatamente igual a um valor não visitado. Utiliza-se uma peneira para acumular frequências e, então, aplica-se a fórmula de contagem de pares com subtração via inclusão-exclusão.

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int MAX_SZ = 1000010;
int arr[MAX_SZ], cnt[MAX_SZ];
int exact_gcd[MAX_SZ];
bool visited[MAX_SZ];
int num;

void solve() {
    cin >> num;
    for (int i = 0; i <= num; i++) {
        visited[i] = false;
        exact_gcd[i] = 0;
        cnt[i] = 0;
        arr[i] = 0;
    }
    int max_elem = 0;
    for (int i = 1; i <= num; i++) {
        cin >> arr[i];
        cnt[arr[i]]++;
        max_elem = max(max_elem, arr[i]);
    }
    for (int i = 1; i <= max_elem; i++)
        for (int j = 2 * i; j <= max_elem; j += i)
            cnt[i] += cnt[j];
    for (int i = max_elem; i > 0; i--) {
        exact_gcd[i] = cnt[i] * (cnt[i] - 1) / 2;
        for (int j = 2 * i; j <= max_elem; j += i)
            exact_gcd[i] -= exact_gcd[j];
    }
    for (int i = 1; i <= num; i++)
        for (int j = arr[i]; j <= max_elem; j += arr[i]) visited[j] = true;
    long long ans = 0;
    for (int i = 1; i <= max_elem; i++)
        if (!visited[i]) ans += exact_gcd[i];
    cout << ans << endl;
}

Essas implementações demonstram como a peneira de primos pode ser adaptada para diversos cenários em programação competitiva, otimizando cálculos relacionados a divisores e MDCs.