Propriedade dos Valores Inteiros de Partes Fracionárias

Considere uma função definida sobre inteiros $x$ dentro do intervalo $[1, n]$. É possível estabelecer que a expressão $\lfloor \frac{k}{\lfloor k/x \rfloor} \rfloor$ retorna o limite superior do bloco onde o valor de $\lfloor k/i \rfloor$ permanece constante.

Dado que a função $f(x) = \frac{k}{x}$ é decrescente em monotonia e analisando as relações de desigualdade:

• $\lfloor \frac{k}{\lflooor k/x \rfloor} \rfloor \ge x$
• $\lfloor \frac{k}{\lfloor k/x \rfloor} \rfloor = \lfloor \frac{k}{x} \rfloor$

Conclui-se que para qualquer índice $i$ compreendido entre $x$ e $\lfloor \frac{k}{\lfloor k/x \rfloor} \rfloor$, o quociente inteiro de $k$ dividido por $i$ não sofre alteração. Essa técnica é fundamental para otimizar somatórios envolvendo partes inteiras.

A Função de Moebius

O coeficiente de Moebius, denotado por $\mu(n)$, é uma função multiplicativa essencial na teoria dos números. Sua definição baseia-se na fatoração prima de $n$: se $n$ possui um fator primo elevado à potência maior ou igual a dois, então $\mu(n) = 0$. Caso contrário, o valor depende da paridade do número de fatores primos distintos:

Implementação via Crivo Linear

Abaixo apresenta-se a rotina em C++ que pré-computa os valores de $\mu$ e identifica números primos simultaneamente.

#pragma GCC optimize("O2")
#include <iostream>
#include <vector>

using namespace std;

const int LIMIT = 6000005;
int primes[LIMIT];
int mobius_cnt = 0;
long long mu[LIMIT];
bool composite[LIMIT]; // Indica se o número não é primo

void precompute_mobius() {
    mu[1] = 1;
    for (int i = 2; i < LIMIT; ++i) {
        if (!composite[i]) {
            primes[++mobius_cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= mobius_cnt && (long long)i * primes[j] < LIMIT; ++j) {
            composite[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                mu[i * primes[j]] = 0;
                break;
            } else {
                mu[i * primes[j]] = -mu[i];
            }
        }
    }
}</vector></iostream>

Convolução de Dirichlet e Transformações

A convolução de Dirichlet entre duas funções aritméticas $f$ e $g$ resulta em uma função $h$, definida pela soma dos produtos ao longo dos divisores:

$h(n) = \sum_{d|n} f(d) \cdot g(\frac{n}{d})$

Se ambas as funções forem multiplicativas, a função resultante também possuirá essa propriedade. Um caso importante para inversão é a relação entre uma função e sua própria convolução com o módulo de Moebius:

• Fórmula de Inversão: $f(n) = \sum_{d|n} g(d) \iff g(n) = \sum_{d|n} \mu(d) f(\frac{n}{d})$
• Identidade Fundamental: $\sum_{d|n} \mu(d) = [n=1]$
• Soma de Euler Totient: $\sum_{d|n} \phi(d) = n$

Triagem de Du Jiao (Du Sieve)

O algoritmo conhecido como Triagem de Du Jiao permite calcular somatórios prefixais de funções multiplicativas complexas em tempo aproximadamente sublinear, utilizando memoização e a propriedade de bloqueio de valores de $\lfloor n/i \rfloor$.

Para uma função alvo $f$ e uma função auxiliar $g$, definimos a convolução $h = f * g$. Então, a soma prefixal $S_h(n)$ relaciona-se com $S_f(n)$ da seguinte forma:

$\sum_{i=1}^{n} h(i) = \sum_{i=1}^{n} g(i) S_f(\lfloor \frac{n}{i} \rfloor)$

Isolando o termo inicial $S_f(n)$ (onde $g(1)=1$ frequentemente simplifica a conta):

Código Completo com Otimização

Exemplo prático aplicando o conceito acima para calcular somatórios de $\phi$ e $\mu$ simultaneamente.

#pragma GCC optimize("O3")
#include <cstdio>
#include <map>

using namespace std;

typedef long long ll;
const int MAX_SIZE = 6000005;

// Estruturas globais para armazenamento
ll phi[MAX_SIZE], mu[MAX_SIZE];
int prime_table[MAX_SIZE];
int total_primes = 0;
bool not_prime[MAX_SIZE];

// Mapas para memoização (hash map simples)
map<ll ll=""> cache_phi;
map<ll ll=""> cache_mu;

// Leitura rápida de entrada
inline ll fast_read() {
    ll res = 0, flag = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') flag = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { res = (res << 1) + (res << 3) + c - 48; c = getchar(); }
    return res * flag;
}

// Pré-processamento linear até o limite fixo
void linear_sieve_init() {
    phi[1] = mu[1] = 1;
    for(int i = 2; i < MAX_SIZE; ++i) {
        if(!not_prime[i]) {
            prime_table[++total_primes] = i;
            phi[i] = i - 1;
            mu[i] = -1;
        }
        for(int j = 1; j <= total_primes && (ll)i * prime_table[j] < MAX_SIZE; ++j) {
            not_prime[i * prime_table[j]] = true;
            if(i % prime_table[j] == 0) {
                mu[i * prime_table[j]] = 0;
                phi[i * prime_table[j]] = phi[i] * prime_table[j];
                break;
            } else {
                mu[i * prime_table[j]] = -mu[i];
                phi[i * prime_table[j]] = phi[i] * (prime_table[j] - 1);
            }
        }
    }
    // Acumulação prefixa para acesso rápido
    for(int i = 1; i < MAX_SIZE; ++i) {
        phi[i] += phi[i-1];
        mu[i] += mu[i-1];
    }
}

// Recursão com memoização para phi
inline ll get_sum_phi(ll n) {
    if(n < MAX_SIZE) return phi[n];
    if(cache_phi.count(n)) return cache_phi[n];
    
    ll total = (1 + n) * n / 2; // Soma de 1 a n
    for(ll l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        total -= (r - l + 1) * get_sum_phi(n / l);
    }
    return cache_phi[n] = total;
}

// Recursão com memoização para mu
inline ll get_sum_mu(ll n) {
    if(n < MAX_SIZE) return mu[n];
    if(cache_mu.count(n)) return cache_mu[n];
    
    ll ans = 1; // Começa em 1 pois [1, n]
    for(ll l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans -= (r - l + 1) * get_sum_mu(n / l);
    }
    return cache_mu[n] = ans;
}

int main() {
    linear_sieve_init();
    ll T_case = fast_read();
    while(T_case--) {
        ll query_n = fast_read();
        printf("%lld %lld\n", get_sum_phi(query_n), get_sum_mu(query_n));
    }
    return 0;
}</ll></ll></map></cstdio>

A estrutura acima substitui a lógica original mantendo a eficiência algébrica, mas adotando nomes mais explícitos e separando a inicialização da consulta. O uso de mapas garante que apenas estados visitados durante a recursão sejam armazenados na memória dinâmica.