Hörmətli (Həll təhlili)

Həll

Əsas müşahidə odur ki, bir tam ədəd $g$ yalnız a_i və a_j ədədləri $g$-nin çoxluqları olduqda (a_i, a_j) cütünün ortaq böləni olur. $C(g)$-ni massiv $a$-da $g$-nin çoxluğu olan elementlərin sayı kimi təyin etsək, onda $g$-nin \gcd(a_i, a_j)-ni bölən cütlərin ümumi sayı aşağıdakı kimi verilir:

Lakin bu dəyər $g$-nin böləni olan hər cütü sayır, mütləq ən böyük ortaq bölən deyil. Məsələn, $2g$ və ya $3g$ olan bir cüt $g$ üçün sayda daxil ediləcəkdir. GCD-nin dəqiq $g$ olduğu cütləri ayırmaq üçün, onun çoxluqlarına aid cütləri çıxarmalıyıq. Biz bunu enən süzgəc istifadə edərək həyata keçiririk. İlk öncə, giriş oxuyarkən $C(g)$ saylarımızı tez bir zamanda yeniləmək üçün 10^5-ə qədər bütün ədədlərin bölənlərini əvvəlcədən hesablayırıq. Hər a_i üçün, onun hər bir böləni üçün sayğacı artırırıq. Biz yalnız C(g) \ge 2 olan $g$ dəyərləri ilə maraqlanırıq, çünki GCD ən azı iki ədəd tələb edir. Sonra $f[g]$-ni GCD-si dəqiq $g$ olan cütlərin sayı kimi təyin edirik. f[g] = \binom{C(g)}{2} ilə başlayırıq. 10^5-dən $1$-ə qədər iterasiya edərək, $g$-ni emal etdiyimiz zaman, artıq onun bütün çoxluqları 2g, 3g, 4g, \dots üçün sayları tamamlanmış olur. Belə bir çoxluq $m$ üçün, $f[m]$-ni $f[g]$-dən çıxarırıq. Bu proses effektiv şəkildə $f[g]$-ni "təmizləyir", belə ki, yalnız GCD-si $g$-dən nə daha böyük, nə də daha kiçik olan cütlərin sayını ehtiva edir.

Bu çıxarışdan sonra, əgər f[g] > 0-dırsa, demək ki, massivdə $g$-nin GCD-si olan ən azı bir cüt var və biz ümumi cavabımızı artırırıq. Hesablamanın mürəkkəbliyi bölənlərin əvvəlcədən hesablanması və süzgəc ilə müəyyən edilir, nəticədə hər test halı üçün effektiv O(A \log A + \sum d(a_i)) olur.

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXA=100005;
vector<int> divs[MAXA];
int cnt[MAXA],f[MAXA];

void pre(){
    for(int i=1;i<MAXA;i++){
        for(int j=i;j<MAXA;j+=i){
            divs[j].push_back(i);
        }
    }
}

void solve(){
    int n;cin>>n;
    vector<int>used;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        for(int d:divs[x]){
            if(!cnt[d])used.push_back(d);
            cnt[d]++;
        }
    }
    vector<int>cand;
    for(int d:used){
        if(cnt[d]>=2)cand.push_back(d);
    }
    sort(cand.rbegin(),cand.rend());
    int ans=0;
    for(int d:cand)f[d]=(cnt[d]*(cnt[d]-1))/2;
    for(int m:cand){
        if(f[m]>0){
            ans++;
            for(int d:divs[m]){
                if(d!=m&&cnt[d]>=2)f[d]-=f[m];
            }
        }
    }
    cout<<ans<<"\n";
    for(int d:used){
        cnt[d]=0;
        f[d]=0;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    pre();
    int t;cin>>t;
    while(t--)solve();
    return 0;
}