Ближній бій#12255

Ближній бій (Розбір)

Автор проблеми:	Tamzid Alahi (Tamzid1) та Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Рішення

Для кожного індексу $i$ визначте ключ класу

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

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

Ми хочемо максимізувати кількість пар $(i, j)$ з $K_{i} = K_{j}$ K_i=K_j, при цьому ми можемо застосувати не більше однієї операції $a_{x} \leftarrow a_{x} + 1$ a_x\leftarrow a_x+1 для одного $x$ .

1) Базовий випадок (без операції). Нехай $cnt [v]$ — частота значення $v$ серед ${K_{i}}$ \{K_i\}. Кількість дійсних пар дорівнює

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

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

2) Спробуйте одне збільшення на $i$ . Якщо ми збільшуємо $a_{i}$ a_i, його ключ стає

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

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

в той час як всі інші $K_{j}$ K_j залишаються незмінними. Внесок пари індексу $i$ змінюється з $cnt [K_{i}] - 1$ \text{cnt}[K_i]-1 на

cnt^{'} [K_{i}^{'}] = {cnt [K_{i}^{'}] cnt [K_{i}] - 1 якщо K_{i}^{'} \neq = K_{i}, якщо K_{i}^{'} = K_{i},

\text{cnt}'[K_i']= \begin{cases} \text{cnt}[K_i'] & \text{якщо } K_i'\ne K_i,\\ \text{cnt}[K_i]-1 & \text{якщо } K_i'=K_i, \end{cases}

оскільки ми концептуально видаляємо $i$ з $cnt [K_{i}]$ \text{cnt}[K_i] спочатку, а потім додаємо його до класу $K_{i}^{'}$ K_i'. Отже, новий загальний результат буде

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).

Ми просто беремо

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

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

Обмеження дають $a_{i} \leq 1 0^{5}$ a_i\le 10^5, тому $a_{i} + 1 \leq 1 0^{5} + 1$ a_i+1\le 10^5+1. Попередньо обчисліть $φ (x)$ для всіх $1 \leq x \leq 100001$ 1\le x\le 100001 один раз, використовуючи лінійний/сито простих чисел.

Складність $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