Introdução à Função Totiente de Euler

A Função Totiente de Euler, denotada como φ(n), determina a contagem de inteiros positivos entre 1 e n que são coprimos com n (ou seja, seu máximo divisor comum é 1). Esta função é uma ferramenta fundamental na teoria dos números e possui propriedades multiplicativas, como φ(a·b) = φ(a)·φ(b) quando a e b são coprimos.

Para um número N com fatoração prima N = p1k1 · p2k2 · ... · pmkm, a função totiente pode ser calculada pela fórmula:

φ(N) = N · (1 - 1/p1) · (1 - 1/p2) · ... · (1 - 1/pm)

Esta expressão mostra que o valor de φ(N) depende apenas dos fatores primos distintos de N, e não de suas potências.

Método de Divisão por Tentativa para um Único Número

Para calcular φ(n) individualmente, utiliza-se a divisão por tentativa. A complexidade temporal é O(√n), pois busca-se fatores primos até a raiz quadrada de n. O algoritmo itera sobre possíveis divisores, atualizando o resultado com base nos fatores primos encontrados.

#include <iostream>

using namespace std;

int calcular_totiente(int num) {
    int resultado = num;
    for (int divisor = 2; divisor * divisor <= num; ++divisor) {
        if (num % divisor == 0) {
            while (num % divisor == 0) {
                num /= divisor;
            }
            resultado -= resultado / divisor;
        }
    }
    if (num > 1) {
        resultado -= resultado / num;
    }
    return resultado;
}

int main() {
    int testes;
    cin >> testes;
    while (testes--) {
        int valor;
        cin >> valor;
        cout << calcular_totiente(valor) << endl;
    }
    return 0;
}

Neste código, a variável resultado é inicializada como n e, para cada fator primo divisor, é subtraída a fração correspondente, replicando a fórmula φ(n) = n · ∏(1 - 1/p) de forma iterativa. O laço while elimina todas as ocorrências do fator primo, garantindo que apenas fatores distintos sejam considerados.

Crivo Linear para Cálculo em Massa

Quando é necessário calcular φ(i) para todos os i até um limite N, pode-se empregar um crivo linear (como o Crivo de Eratóstenes modificado) com complexidade O(N). Este método pré-computa os valores de totiente para todos os números em um intervalo, aproveitando a propriedade multiplicativa da função.

O algoritmo mantém uma lista de primos e, para cada número i, atualiza o totiente de i·p para primos p. Se p divide i, então φ(i·p) = φ(i)·p; caso contrário, φ(i·p) = φ(i)·(p - 1). A soma de todos os totientes pode ser acumulada durante o processo.

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int MAXIMO = 1000010;

int main() {
    int n;
    cin >> n;

    vector<int> primos;
    vector<bool> eh_primo(MAXIMO + 1, true);
    vector<int> totiente(MAXIMO + 1, 0);
    ll soma = 0;

    totiente[1] = 1;

    for (int i = 2; i <= n; ++i) {
        if (eh_primo[i]) {
            primos.push_back(i);
            totiente[i] = i - 1;
            soma += totiente[i];
        }

        for (size_t j = 0; j < primos.size(); ++j) {
            int p = primos[j];
            if (i * p > n) break;
            eh_primo[i * p] = false;

            if (i % p == 0) {
                totiente[i * p] = totiente[i] * p;
                soma += totiente[i * p];
                break;
            }
            totiente[i * p] = totiente[i] * (p - 1);
            soma += totiente[i * p];
        }
    }

    cout << soma + 1 << endl;

    return 0;
}

Neste código, totiente[i] armazena φ(i), e soma acumula os totientes de 2 a n, com o valor de φ(1) adicionado explicitamente na saída. A estrutura do crivo assegura que cada número seja processado em tempo constante amortizado, resultando em eficiência linear.