CF2045K GCDDCG
首先我们发现我们需要求出每个 \(i\) 的答案，考虑莫反，枚举第一组的 gcd 是 \(x\) 的倍数第二组的是 \(y\) 的倍数，设 \(b_x\) 表示 \(a\) 是 \(x\) 的倍数的个数。
假设我们不考虑空集的情况，因为那部分平凡，那么式子就是：
\[\sum\limits_{i\mid x} \sum\limits_{i\mid y} \mu\Big(\frac{x}{i}\Big) \times \mu\Big(\frac{y}{i}\Big) \times 2^{b_x - b_{[x,y]}} \times 2^{b_y - b_{[x,y]}} \times 3^{b_{[x,y]}} = \sum\limits_{i\mid x} \sum\limits_{i\mid y} \mu\Big(\frac{x}{i}\Big) \times \mu\Big(\frac{y}{i}\Big) \times 2^{b_x} \times 2^{b_y} \times {\Big (\frac{3}{4} \Big )}^{b_{[x,y]}}
\]
直接做会超时，考虑优化这个东西。
我们发现难点在于 \([x,y]\)，我们发现这个东西是 \(n^2\) 量级的，但是所有 \([x,y]>n\) 只会造成 \(1\) 的贡献，我们可以整体提出来这样我们就把值域缩成了 \(n\) 的量级。
注意到如果我们枚举 \([x,y]\)，那么我们这个东西实际上就是干一个 lcm 卷积。
\[h(n)=\sum_{[x,y]=n} f(x)g(y)
\]
设 \(H(n) = \sum\limits_{d\mid n} h(d)\)，\(F(n),G(n)\) 同理。
那么我们发现 \(F(n)G(n) = (\sum\limits_{x\mid n} f(x))(\sum\limits_{y\mid n} g(y)) = \sum\limits_{[x,y]\mid n} f(x)g(y) = H(n)\)，这就是个点值乘法，最后我们莫反得到 \(h\) 即可，模拟上述过程复杂度 \(O(n\ln^2 n)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=998244353;
int a[N],n,b[N],mp[N],mu[N],vis[N],pr[N],cnt,f[N],h[N],pw[N];
inline int read(){char c=getchar();int ans=0,f=1;while(c<48||c>57) (c==45?f=-1:1),c=getchar();while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();return ans*f;
}
inline void add(int &x,int y){x=(x+y)%mod;}
inline int qpow(int a,int b){int s=1;while(b){(b&1)?s=s*a%mod:1,a=a*a%mod,b>>=1;}return s;}
void exgcd(int a,int b,int &x,int &y){if (b==0) x=1,y=0;else exgcd(b,a%b,y,x),y-=a/b*x%mod;}
inline int inv(int a){int x,y;exgcd(a,mod,x,y);return (x%mod+mod)%mod;}
inline void init(int n){mu[1]=1;for (int i=2;i<=n;i++){if (!vis[i]) pr[++cnt]=i,mu[i]=-1;for (int j=1;i*pr[j]<=n;j++){vis[i*pr[j]]=1;if (i%pr[j]==0) break;mu[i*pr[j]]=-mu[i];}}for (int i=1;i<=n;i++) mu[i]=(mu[i]+mod)%mod;
}
main(){n=read();init(n);for (int i=1;i<=n;i++) mp[a[i]=read()]++;pw[0]=1;for (int i=1;i<=n;i++) pw[i]=pw[i-1]*2%mod;for (int i=1;i<=n;i++) for (int j=i;j<=n;j+=i) b[i]+=mp[j];int ans=0;for (int i=1;i<=n;i++){int sum=0,sum1=0,sum2=0;for (int x=i;x<=n;x+=i) add(sum1,pw[b[x]]*mu[x/i]%mod),add(sum2,mu[x/i]);for (int x=i;x<=n;x+=i) add(sum,mu[x/i]*(mod+pw[b[x]]-1)%mod*sum2%mod+mu[x/i]*sum1%mod);add(ans,mod-i*sum%mod+i*sum1%mod*sum1%mod);for (int x=i;x<=n;x+=i) for (int y=x;y<=n;y+=x) add(f[y],mu[x/i]*pw[b[x]]%mod);for (int x=i;x<=n;x+=i) f[x]=f[x]*f[x]%mod;for (int x=i;x<=n;x+=i) for (int y=x;y<=n;y+=x) add(h[y],mu[y/x]*f[x]%mod);for (int x=i;x<=n;x+=i) add(ans,i*h[x]%mod*(qpow(3*inv(4)%mod,b[x])-1+mod)%mod),f[x]=h[x]=0;} cout <<ans<<endl;return 0;
}