Combate Cercano#12255

Combate Cercano (Editorial)

Autor del Problema:	Tamzid Alahi (Tamzid1) y Hasan Saleh (MathModel)
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución

Para cada índice $i$ , define la clave de clase

K_{i} = lcm (i, φ (a_{i})) .

K_i=\operatorname{lcm}\big(i,\ \varphi(a_i)\big).

Queremos maximizar el número de pares $(i, j)$ con $K_{i} = K_{j}$ K_i=K_j, mientras podemos aplicar como máximo una operación $a_{x} \leftarrow a_{x} + 1$ a_x\leftarrow a_x+1 para un solo $x$ .

1) Línea base (sin operación). Deja que $cnt [v]$ sea la frecuencia del valor $v$ entre ${K_{i}}$ \{K_i\}. El número de pares válidos es

pares_{0} = v \sum (2 cnt [ v ]) .

\text{pares}_0=\sum_v \binom{\text{cnt}[v]}{2}.

2) Intenta un incremento en $i$ . Si aumentamos $a_{i}$ a_i, su clave se convierte en

K_{i}^{'} = lcm (i, φ (a_{i} + 1)),

K_i'=\operatorname{lcm}\big(i,\ \varphi(a_i+1)\big),

mientras que todos los demás $K_{j}$ K_j permanecen iguales. La contribución de pares del índice $i$ cambia de $cnt [K_{i}] - 1$ \text{cnt}[K_i]-1 a

cnt^{'} [K_{i}^{'}] = {cnt [K_{i}^{'}] cnt [K_{i}] - 1 si K_{i}^{'} \neq = K_{i}, si K_{i}^{'} = K_{i},

\text{cnt}'[K_i']= \begin{cases} \text{cnt}[K_i'] & \text{si } K_i'\ne K_i,\\ \text{cnt}[K_i]-1 & \text{si } K_i'=K_i, \end{cases}

porque conceptualizamos eliminar $i$ de $cnt [K_{i}]$ \text{cnt}[K_i] primero, luego lo agregamos a la clase de $K_{i}^{'}$ K_i'. Por lo tanto, el nuevo total es

pares_{i} = pares_{0} - (cnt [K_{i}] - 1) + (cnt [K_{i}^{'}] - 1_{K_{i}^{'} = K_{i}}) .

\text{pares}_i=\text{pares}_0-\big(\text{cnt}[K_i]-1\big)+\big(\text{cnt}[K_i']-\mathbf{1}_{K_i'=K_i}\big).

Simplemente tomamos

max (pares_{0}, i max pares_{i}) .

\max\big(\text{pares}_0,\ \max_i \text{pares}_i\big).

Las restricciones dan $a_{i} \leq 1 0^{5}$ a_i\le 10^5, así que $a_{i} + 1 \leq 1 0^{5} + 1$ a_i+1\le 10^5+1. Precomputamos $φ (x)$ para todos $1 \leq x \leq 100001$ 1\le x\le 100001 una vez usando un estilo de criba de totientes lineal/primal.

Complejidad $O (1 0^{5} lo g lo g 1 0^{5} + \sum n)$ \mathcal{O}(10^5 \log \log 10^5+\sum n)

import math

M=100001
phi=list(range(M+1))
for p in range(2,M+1):
    if phi[p]==p:
        for x in range(p,M+1,p):
            phi[x]-=phi[x]//p

def lcm(a,b): 
    return a//math.gcd(a,b)*b

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    K=[lcm(i+1, phi[a[i]]) for i in range(n)]
    from collections import Counter
    cnt=Counter(K)
    base=sum(c*(c-1)//2 for c in cnt.values())
    ans=base
    for i in range(n):
        x=K[i]
        y=lcm(i+1, phi[a[i]+1])
        cx=cnt[x]
        cy=cnt.get(y,0)
        if y==x:
            cur=base 
        else:
            cur=base-(cx-1)+cy
        if cur>ans: ans=cur
    print(ans)

Python