2020 ccpc 吉林省賽 H

2020 ccpc 吉林省賽 H

題意：

給一組數 a i a_i ai?,求 ∑ i = 1 n ∑ j = 1 n [ g c d ( a i , a j ) = d ] \sum\limits_{i=1}^n\sum\limits_{j=1}^{n}[gcd(a_i,a_j)=d] i=1∑n?j=1∑n?[gcd(ai?,aj?)=d]

在賽場上我當時腦抽寫了個假的演算法，看似是 O ( T m l o g m ) O(Tmlogm) O(Tmlogm)，但實際上是 O ( T m k ) O(Tmk) O(Tmk),只能說這道題的出題人真的沒有認真出資料，沒有全為1的 x的資料，結果我跑過去才發現假了，現在補個正解

首先裸的莫比烏斯反演，直接上套路秒了,我當時傻叉了換了另一種方式反演

g ( d ) = ∑ i = 1 n ∑ j = 1 n [ g c d ( a i , a j ) = d ] g(d)=\sum\limits_{i=1}^n\sum\limits_{j=1}^{n}[gcd(a_i,a_j)=d] g(d)=i=1∑n?j=1∑n?[gcd(ai?,aj?)=d]

f ( x ) = ∑ x ∣ d g ( d ) = ∑ i = 1 n ∑ j = 1 n ∑ x ∣ d [ g c d ( a i , a j ) = d ] = ∑ i = 1 n ∑ j = 1 n [ x ∣ a i 且 x ∣ a j ] f(x)=\sum_{x|d}g(d)=\sum\limits_{i=1}^n\sum\limits_{j=1}^{n}\sum_{x|d}[gcd(a_i,a_j)=d]=\sum\limits_{i=1}^n\sum\limits_{j=1}^{n}[x|ai且x|aj] f(x)=∑x∣d?g(d)=i=1∑n?j=1∑n?∑x∣d?[gcd(ai?,aj?)=d]=i=1∑n?j=1∑n?[x∣ai且x∣aj]

g ( n ) = ∑ n ∣ d m u ( d n ) f ( d ) g(n)=\sum_{n|d}mu(\frac{d}{n})f(d) g(n)=∑n∣d?mu(nd?)f(d)

g 和 f 都 可 以 在 一 組 中 由 于 調 和 級 數 在 O ( n l o g n ) 時 間 內 處 理 出 來 ， 復 雜 度 O ( T n l o g n ) , 具 體 看 代 碼 g和f都可以在一組中由于調和級數在O(nlogn)時間內處理出來，復雜度O(Tnlogn),具體看代碼 g和f都可以在一組中由于調和級數在O(nlogn)時間內處理出來，復雜度O(Tnlogn),具體看代碼

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int mu[maxn],prime[maxn],t,n,m,k,a;
bool v[maxn];
ll cnt[maxn],cnt_ans[maxn],ans[maxn],tot;
void init(){ 
    mu[1]=1;
    for(int i=2;i<maxn;++i){ 
        if(!v[i])prime[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&prime[j]*i<maxn;++j){ 
            v[i*prime[j]]=1;
            if(i%prime[j]==0) 
                break;
            mu[i*prime[j]]=-mu[i];
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); 
    init();
    cin>>t;
    while(t--){ 
        cin>>n>>m>>k;
        for(int i=1;i<=m;++i)ans[i]=cnt_ans[i]=cnt[i]=0;
        for(int i=1;i<=n;++i){ 
            cin>>a;cnt[a]++;
        }
        for(int i=1;i<=m;++i){ 
            for(int j=i;j<=m;j+=i){ 
                cnt_ans[i]+=cnt[j];
            }
        }
        for(int i=1;i<=m;++i){ 
            for(int j=i;j<=m;j+=i){ 
                ans[i]+=cnt_ans[j]*cnt_ans[j]*mu[j/i];
            }
        }
        for(int i=1;i<=k;++i){ 
            cin>>a;
            cout<<ans[a]<<"\n";
        }
    }
    return 0;
}