Problem AGC038C
给定一个长为 \(n\) 的序列 \(A_1,A_2,\cdots,A_n\)，求 \(\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{lcm(A_i,A_j)}} \bmod 998244353\)
\(n\leq 2\times 10^5,A_i \leq 10^6\)
Time Limit: 2 sec / Memory Limit: 1024 MB
Analytics
我们发现这个 \(j\) 的下标是从 \(i+1\) 起枚举的，因此我们考虑变形：
\[\begin{align*} Ans&=\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{lcm(A_i,A_j)}}\\ &=\frac{\sum_{i=1}^{n}{\sum_{j=1}^{n}{lcm(A_i,A_j)}}-\sum_{i=1}^{n}{A_i}}{2} \end{align*} \]记 \((1)=\sum_{i=1}^{n}{\sum_{j=1}^{n}{\mathrm{lcm(A_i,A_j)}}},MAX=\max(A_i)\)，问题化为如何求 \((1)\)：
\[\begin{align*} (1)&=\sum_{i=1}^{n}{\sum_{j=1}^{n}{\frac{A_iA_j}{gcd(A_i,A_j)}}}\\ &=\sum_{d=1}^{MAX}{d^{-1}\sum_{i=1}^{n}{\sum_{j=1}^{n}{A_iA_j[gcd(A_i,A_j)=d]}}}\\ &=\sum_{d=1}^{MAX}{d^{-1}\sum_{i=1}^{n}{\sum_{j=1}^{n}{A_iA_j[d\mid A_i][d\mid A_j][gcd(\frac{A_i}{d},\frac{A_j}{d})=1]}}} \end{align*} \]显然后面那个 \([gcd=1]\) 的式子可以反演，因此
\[\begin{align*} (1)&=\sum_{d=1}^{MAX}{d^{-1}\sum_{i=1}^{n}{\sum_{j=1}^{n}{A_iA_j[d\mid A_i][d\mid A_j]\sum_{k\mid \frac{A_i}{d},\frac{A_j}{d}}{\mu(k)}}}}\\ &=\sum_{d=1}^{MAX}{d^{-1}\sum_{k=1}^{\frac{MAX}{d}}{\mu(k)\sum_{i=1}^{n}{\sum_{j=1}^{n}{A_iA_j[dk\mid A_i][dk\mid A_j]}}}} \end{align*} \]观察 \(\sum_{i=1}^{n}{\sum_{j=1}^{n}{A_iA_j[dk\mid A_i][dk\mid A_j]}}\) 这个式子，我们发现：
\[\begin{align*} \sum_{i=1}^{n}{\sum_{j=1}^{n}{A_iA_j[dk\mid A_i][dk\mid A_j]}}&=\sum_{i=1}^{n}{A_i[dk\mid A_i]\sum_{j=1}^{n}{A_j[dk\mid A_j]}}\\ &=(\sum_{i=1}^{n}{A_i[dk\mid A_i]})^2 \end{align*} \]因此我们可以定义一个 sum[MAX] ，\(sum_v\) 表示序列 \(A\) 中所有满足 \(v\mid A_i\) 的元素之和。
记 \(V\) 为值域，输入时枚举因数即可 \(O(n\sqrt V)\) 地预处理出所需的 \(fac\)，最终
\[(1)=\sum_{d=1}^{MAX}{d^{-1}\sum_{k=1}^{\frac{MAX}{d}}{\mu(k)(sum_{dk})^2}} \]注意这里不能为了避免计算逆元变形为 \((1)=\sum_{d=1}^{MAX}{d\sum_{k=1}^{\frac{MAX}{d}}{\mu(k)(\frac{sum_{dk}}{d})^2}}\) ，原因很简单，你能保证\(sum_{dk} \bmod 998244353\) 后仍能被 \(d\) 整除吗。
那么，这两层 \(\sum\) 的复杂度如何呢？
由简单的微积分知识我们知道调和级数的复杂度是 \(\ln\) 量级的
具体地，\(\sum_{i=1}^{n}{\frac{1}{i}}>\int_{1}^{n+1}{\frac{1}{x}dx}=\ln(n+1)\)
因此计算 \((1)\) 的复杂度仅有 \(O(V\ln V)\) ，最终时间复杂度为 \(O(V\ln V+n \sqrt V)\)，可以通过此题。
求出 \((1)\) 后，得到\(Ans=\frac{(1)-sum_1}{2}\)（因为任何整数都能被\(1\)整除，所以 \(sum_1\) 即所有元素和）
Hint: 最后别忘了判一下因为取模导致的 \((1)-sum_1\) 为奇数或负数的情况。
Code
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
inline int qpow(int a,int b,int p){
int res=1;
while(b){
if(b&1) res=1LL*res*a%p;
a=1LL*a*a%p;b>>=1;
}
return res;
}
using i64=long long;
const int N=1e6+5,mod=998244353;
int sum[N],mu[N],MAX=0;
bool vis[N];
vector<int> prime;
inline void sieve(){ //线性筛预处理mu函数
mu[1]=1;
for(register int i=2;i<N;++i){
if(!vis[i]) prime.push_back(i),mu[i]=-1;
for(register int j=0;j<prime.size()&&prime[j]*i<N;++j){
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
mu[i*prime[j]]=-mu[i];
}
}
}
inline void read(int& x){
char ch=getchar();x=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}
int main(){
sieve();
int n,now;read(n);
for(register int i=1;i<=n;++i){
read(now);
MAX=max(MAX,now);
int j;
for(j=1;j*j<now;++j){ //枚举因数预处理
if(!(now%j)){
(sum[j]+=now)%=mod;
(sum[now/j]+=now)%=mod;
}
}
if(j*j==now) (sum[j]+=now)%=mod;
}
int ans=0,res=0;
for(register int d=1;d<=MAX;++d,res=0){
for(register int k=1;k<=MAX/d;++k){
res=(1LL*mu[k]*sum[k*d]*sum[k*d]%mod+res)%mod;
}
ans=(1LL*qpow(d,mod-2,mod)*res+ans)%mod;//qpow(d,mod-2,mod)为逆元
}
int v1=ans,v2=sum[1];
int ok=(v1&1)^(v2&1); //特判
if(ok) ans=(1LL*v1+mod-v2)/2%mod;
else ans=(1LL*v1+mod+mod-v2)/2%mod;
printf("%d",ans);
return 0;
}