Abordagem via Funções Geradoras de Dirichlet

Este problema pode ser resolvido sem utilizar funções geradoras de Dirichlet (DGF), através de combinatória direta. No entanto, a abordagem com DGF oferece uma perspectiva mais elegante e sistemática.

Definição do Operador Derivada

Para uma função aritmética f, definimos sua derivada como:

f'(n) = f(n) × ω(n)

onde ω(n) representa a soma dos expoentes na fatoração prima de n (isto é, o número total de fatores primários com multiplicidade).

Logaritmo e Exponencial de Funções Aritméticas

Utilizando esta definição de derivada, podemos estabelecer as seguintes relações fundamentais:

Logaritmo

A derivada do logaritmo de uma função satisfaz:

ln(F)' = F'/F

Expandindo esta expressão em termos de convolução de Dirichlet:

ln(F)[n] × ω(n) = F[n] × ω(n) - Σ(d|n, d<n) ln(F)[d] × ω(d) × F[n/d]

Exponencial

Para a exponencial, temos:

(e^F)' = e^F × F'

Que se traduz em:

exp(F)[n] × ω(n) = Σ(d|n) exp(F)[d] × F[n/d] × ω(n/d)

Note que após aplicar o logaritmo, temos F[1] = 0, o que implica:

exp(F)[n] × ω(n) = Σ(d|n, d<n) exp(F)[d] × F[n/d] × ω(n/d)

Potenciação k-vezes

Para calcular G = F^k, podemos utilizar as propriedades do logaritmo:

G = F^k
ln(G) = k × ln(F)
G'/G = k × F'/F
G' × F = k × F' × G

Em termos de convolução de Dirichlet:

Σ(d|n) G[d] × ω(d) × F[n/d] = k × Σ(d|n) F[d] × ω(d) × G[n/d]

Considerando que ω(1) = 0, obtemos:

G[n] × ω(n) × F[1] = k × Σ(d|n, d>1) F[d] × ω(d) × G[n/d] - Σ(d|n, d<n) G[d] × ω(d) × F[n/d]

Observação Importante

Assim como em polinômios, ao aplicar as operações de logaritmo e exponencial, o termo constante (valor em 1) deve ser igual a 1. Caso contrário, é necessário normalizar a função antes de realizar estas operações.

Implementação

A seguir, apresentamos uma implementação em C++ que utiliza a abordagem descrita:

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MOD = 1000000007;

int composites[MAXN];
int primes[MAXN], primeCount;
int omegaValues[MAXN];

void computePrimes(int limit) {
    for (int i = 2; i <= limit; i++) {
        if (!composites[i]) {
            primes[++primeCount] = i;
            omegaValues[i] = 1;
        }
        for (int j = 1; i * primes[j] <= limit; j++) {
            int product = i * primes[j];
            composites[product] = 1;
            omegaValues[product] = omegaValues[i] + 1;
            if (i % primes[j] == 0) break;
        }
    }
}

long long modPow(long long base, long long exponent) {
    long long result = 1;
    base %= MOD;
    while (exponent) {
        if (exponent & 1) result = result * base % MOD;
        base = base * base % MOD;
        exponent >>= 1;
    }
    return result;
}

int T, N, K;
vector<int> divisors[MAXN];
long long inputArray[MAXN];
long long functionG[MAXN];
long long auxiliaryH[MAXN];

void processTestCase() {
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) scanf("%lld", &inputArray[i]);
    
    for (int i = 1; i <= N; i++) {
        divisors[i].clear();
        for (int j = 1; j * i <= N; j++) {
            divisors[i * j].push_back(i);
        }
    }
    
    auxiliaryH[1] = 0;
    for (int i = 2; i <= N; i++) {
        auxiliaryH[i] = omegaValues[i];
        for (int d : divisors[i]) {
            if (d < i) {
                auxiliaryH[i] = (auxiliaryH[i] - auxiliaryH[d]) % MOD;
            }
        }
    }
    
    for (int i = 1; i <= N; i++) {
        auxiliaryH[i] = auxiliaryH[i] * K % MOD;
    }
    
    functionG[1] = 1;
    for (int i = 2; i <= N; i++) {
        functionG[i] = 0;
        for (int d : divisors[i]) {
            if (d < i) {
                functionG[i] = (functionG[i] + functionG[d] * auxiliaryH[i / d]) % MOD;
            }
        }
        functionG[i] = functionG[i] * modPow(omegaValues[i], MOD - 2) % MOD;
    }
    
    for (int i = 1; i <= N; i++) {
        long long answer = 0;
        for (int d : divisors[i]) {
            answer = (answer + inputArray[d] * functionG[i / d]) % MOD;
        }
        answer = (answer % MOD + MOD) % MOD;
        printf("%lld ", answer);
    }
    printf("\n");
}

int main() {
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);
    
    computePrimes(100000);
    scanf("%d", &T);
    
    for (int test = 1; test <= T; test++) {
        processTestCase();
    }
    
    return 0;
}

Esta implementação segue o seguinte fluxo:

1. Pré-calcular os valores de ω(n) para todos os n até o limite necessário usando o crivo de Eratóstenes
2. Para cada caso de teste, construir a lista de divisores para todos os números
3. Calcular a função auxiliar h utilizando a fórmula de derivada logarítmica
4. Computar a função final g usando exponenciação k-vezes
5. Para cada posição i, calcular a resposta como convolução dos valores de entrada com a função g

A complexidade desta solução é O(N log N) por caso de teste, onde N é o valor máximo de n.