Yaxın Döyüş#12255

Yaxın Döyüş (Həll təhlili)

Problem Müəllifi:	Tamzid Alahi (Tamzid1) və Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Hər bir indeks $i$ üçün sinif açarını müəyyən edin

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

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

Biz $K_{i} = K_{j}$ K_i=K_j olan $(i, j)$ cütlərinin sayını maksimuma çatdırmaq istəyirik, eyni zamanda bir dəfə əməliyyat $a_{x} \leftarrow a_{x} + 1$ a_x\leftarrow a_x+1 tətbiq etməyə icazə verilir.

1) Əsas xətt (əməliyyatsız). $cnt [v]$ dəyəri $v$ olan ${K_{i}}$ \{K_i\} arasında tezliyi olsun. Etibarlı cütlərin sayı

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

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

2) $i$ -də bir artırma cəhd edin. Əgər $a_{i}$ a_i-ni artırsaq, onun açarı

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

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

bütün digər $K_{j}$ K_j eyni qalır. İndeks $i$ -nin cütlərə töhfəsi $cnt [K_{i}] - 1$ \text{cnt}[K_i]-1-dən

cnt^{'} [K_{i}^{'}] = {cnt [K_{i}^{'}] cnt [K_{i}] - 1 əgər K_{i}^{'} \neq = K_{i}, əgər K_{i}^{'} = K_{i},

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

şəklində dəyişir, çünki biz konseptual olaraq əvvəlcə $i$ -ni $cnt [K_{i}]$ \text{cnt}[K_i]-dən çıxarırıq, sonra isə onu $K_{i}^{'}$ K_i' sinfinə əlavə edirik. Beləliklə, yeni cəmi

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

Sadəcə olaraq

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

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

alırıq.

Məhdudiyyətlər $a_{i} \leq 1 0^{5}$ a_i\le 10^5 verir, buna görə də $a_{i} + 1 \leq 1 0^{5} + 1$ a_i+1\le 10^5+1. $φ (x)$ -i $1 \leq x \leq 100001$ 1\le x\le 100001 üçün bir dəfə xətti/başqa bir üsul ilə əvvəlcədən hesablayın.

Komplekslik $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