Combat de Proximité#12255

Combat de Proximité (Corrigé)

Auteur du Problème:	Tamzid Alahi (Tamzid1) et Hasan Saleh (MathModel)
Préparé par:	Hasan Saleh (MathModel)
Édité par:	Hasan Saleh (MathModel)

Solution

Pour chaque indice $i$ , définissez la clé de classe

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

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

Nous voulons maximiser le nombre de paires $(i, j)$ avec $K_{i} = K_{j}$ K_i=K_j, tout en pouvant appliquer au maximum une opération $a_{x} \leftarrow a_{x} + 1$ a_x\leftarrow a_x+1 pour un seul $x$ .

1) Baseline (pas d'opération). Soit $cnt [v]$ la fréquence de la valeur $v$ parmi ${K_{i}}$ \{K_i\}. Le nombre de paires valides est

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

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

2) Essayer un incrément à $i$ . Si nous augmentons $a_{i}$ a_i, sa clé devient

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

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

tandis que toutes les autres $K_{j}$ K_j restent les mêmes. La contribution de paire de l'indice $i$ passe de $cnt [K_{i}] - 1$ \text{cnt}[K_i]-1 à

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}

car nous retirons conceptuellement $i$ de $cnt [K_{i}]$ \text{cnt}[K_i] d'abord, puis l'ajoutons à la classe de $K_{i}^{'}$ K_i'. Ainsi, le nouveau total est

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

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

Nous prenons simplement

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

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

Les contraintes donnent $a_{i} \leq 1 0^{5}$ a_i\le 10^5, donc $a_{i} + 1 \leq 1 0^{5} + 1$ a_i+1\le 10^5+1. Pré-calculer $φ (x)$ pour tous $1 \leq x \leq 100001$ 1\le x\le 100001 une fois en utilisant un crible de totient de style linéaire/prime.

Complexité $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