Problema D: Definição Estranha

Definimos dois números como adjacentes se o resultado de lcm(a,b)/gcd(a,b) for um quadrado perfeito. Dada uma sequência de comprimento n, para cada elemento a[i], d[i] é a contagem de elementos adjacentes a ele. A cada segundo, cada elemento se transforma no produto dele mesmo com todos os seus elementos adjacentes. Para q consultas, dado x, devemos retornar o maior d[i] após x segundos.

A solução envolve fatorar os números e calcular um "produto ímpar" — o produto de todos os fatores primos com expoente ímpar na decomposição. Números com o mesmo produto ímpar são adajcentes. Ao agrupar esses produtos, observamos que grupos com tamanho par (ou produto ímpar igual a 1) se fundem após uma transformação, enquento grupos com tamanho ímpar permanecem isolados. Portanto, para x=0, a resposta é o maior tamanho de grupo; para x>0, a resposta é o máximo entre o maior tamanho de grupo e a soma dos tamanhos dos grupos que se fundem.

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
#define N 300005
#define INF 999999999
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline ll read(){ll x;scanf("%lld",&x);return x;}
unordered_map<ll,ll> agrupamento;
ll maxInicial, maxFinal, somaTotal;

void calcularProdutoImpar(ll valor) {
    ll produto=1, temp=valor;
    for(int i=2;i*i<=valor;++i) {
        if(valor%i==0) {
            int cont=0;
            while(valor%i==0) cont++, valor/=i;
            if(cont%2) produto*=i; 
        }
    }
    if(valor!=1) produto*=valor;
    agrupamento[produto]++;
}

void resolver() {
    somaTotal=maxInicial=maxFinal=0;
    agrupamento.clear();
    ll n=read();
    f(i,1,n) calcularProdutoImpar(read());
    for(auto& par : agrupamento) {
        maxInicial=max(maxInicial, par.second);
        if(par.second%2==0 || par.fi==1)
            somaTotal+=par.second;
    }
    maxFinal=max(maxInicial, somaTotal);
    ll q=read();
    f(i,1,q) {
        ll x=read();
        if(!x) printf("%lld\n", maxInicial);
        else printf("%lld\n", maxFinal);
    }
}

int main() {
    ll T=read();
    while(T--) resolver();
    return 0;
}

Problema F: Habitação Estranha

Dado um grafo não direcionado e sem peso, precisamos selecionar alguns vértices para colorir, de modo que: 1) todo vértice seja colorido ou adjacente a um vértice colorido; 2) o grafo permaneça conectado; 3) vértices coloridos não sejam adjacentes. Encontrar tal coloração ou reportar "NO".

A abordagem utiliza busca em profundidade (DFS). Partindo de um vértice inicial, para cada vértice visitado, se nenhum de seus vizinhos foi colorido, colorimos o vértice atual; caso contrário, não o colorimos. Isso garante as condições 1 e 3. A conectividade é mantida pela natureza da DFS em grafos conexos.

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
#define N 300005
#define INF 999999999
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline ll read(){ll x;scanf("%lld",&x);return x;}
vector<ll> grafo[N], resultado;
int estado[N];

void buscaProfundidade(ll no) {
    estado[no]=2;
    for(ll vizinho : grafo[no]) {
        if(estado[vizinho]==2) estado[no]=1;
    }
    for(ll vizinho : grafo[no]) {
        if(!estado[vizinho]) buscaProfundidade(vizinho);
    }
}

void resolver() {
    ll n=read(), m=read();
    resultado.clear();
    f(i,1,n) estado[i]=0, grafo[i].clear();
    f(i,1,m) {
        ll u=read(), v=read();
        grafo[u].pb(v);
        grafo[v].pb(u);
    }
    buscaProfundidade(1);
    int contador=0;
    f(i,1,n) {
        if(!estado[i]) {
            printf("NO\n");
            return;
        }
        if(estado[i]==2) resultado.pb(i);
    }
    printf("YES\n");
    int tamanho=resultado.size();
    printf("%d\n", tamanho);
    for(ll x : resultado) printf("%lld ", x);
    printf("\n");
}

int main() {
    ll T=read();
    while(T--) resolver();
    return 0;
}

Notas Técnicas

O conceito de "produto ímpar" é útil em problemas que envolvem paridade de expoentes na fatoração prima, permitindo agrupar números por adjacência defindia por razões de lcm e gcd.

Para decomposição rápida de fatores primos em intervalos até 10^6, podemos pré-calcular o menor fator primo para cada número usando crivo, resultando em complexidade O(n log n) para pré-processamento e O(log n) por consulta.

int menorFator[N];
void preprocessarCrivo(int limite) {
    for(int i=2; i<=limite; ++i) {
        if(menorFator[i]) continue;
        for(int j=i; j<=limite; j+=i)
            menorFator[j]=i;
    }
}