其实不会反演也可以做。
首先显然要考虑给你每个数个数，怎么计数。最简单的方法是从大枚举到小，设 \(c_i\) 为 \(i\) 的个数，\(f_i\) 为 \(\gcd=i\) 的 \(k\) 元组出现了多少次，则 \(f_i=\binom{c_i}{k}-\sum_j f_{ij}\)，就是 \(\gcd\) 为 \(i\) 或 \(i\) 的倍数减去 \(\gcd\) 为 \(i\) 的倍数的。
这样单次是 \(O(V\ln V)\) 的。考虑怎么高效地处理修改。每次只有 \(d(b_j)\) 个 \(c_i,f_i\) 被修改，所以可以预处理每个数的所有因数然后暴力修改。
但是一个 \(c_i\) 修改完后也会影响所有 \(j\mid i\) 的 \(c_j\)，怎么办呢？
打表发现 \(10^6\) 以内，对于一个 \(x\)，他的所有因数的因数之和大概在 \(8000\) 到 \(9000\) 之间。结合本题时间限制可以通过。具体实现是计算完 \(f_x\) 的增加量后，以此修改所有 \(y|x\) 的 \(f_y\) 的增加量。
code：
点击查看代码
int n,m,k=1e6,q,c[N],d[N],f[N],fac[N],ifac[N];
vector<int> g[N];
il int Mod(int x,int y){return x+y>=mod?x+y-mod:x+y;}
il int binom(int x,int y){
if(x<0||y<0||x<y)return 0;
return 1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
il int qpow(int x,int y){
int ret=1;
while(y){
if(y&1)ret=1ll*ret*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return ret;
}
void Yorushika(){
scanf("%d%d%d",&n,&m,&q);
rep(i,1,n){
int x;scanf("%d",&x);
c[x]++;
}
fac[0]=1;
rep(i,1,k)fac[i]=1ll*fac[i-1]*i%mod;
ifac[k]=qpow(fac[k],mod-2);
drep(i,k-1,0)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
rep(i,1,k){
for(int j=i+i;j<=k;j+=i)c[i]+=c[j],g[j].eb(i);
}
int ans=0;
drep(i,k,1){
f[i]=binom(c[i],m);
for(int j=i+i;j<=k;j+=i)f[i]=Mod(f[i],mod-f[j]);
ans=Mod(ans,1ll*f[i]*i%mod);
}
while(q--){
int x;scanf("%d",&x);
for(int i:g[x])d[i]=0;
d[x]=Mod(binom(c[x]+1,m),mod-binom(c[x],m)),c[x]++,ans=Mod(ans,1ll*x*d[x]%mod);
for(int i:g[x])d[i]=Mod(d[i],mod-d[x]);
drep(i,(int)g[x].size()-1,0){
int y=g[x][i];
d[y]=Mod(d[y],Mod(binom(c[y]+1,m),mod-binom(c[y],m))),c[y]++,ans=Mod(ans,1ll*y*d[y]%mod);
for(int j:g[y])d[j]=Mod(d[j],mod-d[y]);
}
printf("%d\n",ans);
}
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}