LCM
首先
\[\sum_{i=1}^{n}i=\dfrac{n*(n+1)}{2} \]\[\sum_{i=1}^{n}i^2=\dfrac{n*(n+1)*(2n+1)}{6} \]\[\sum_{i=1}^{n}i^3=(\sum_{i=1}^{n}i)^2 \]P3911 最小公倍数之和
\[\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(A_i,A_j) \]观察值域，发现与 \(n\) 同阶，记 \(c_i\) 表示数字 i 出现次数。
\[\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j)*c_i*c_j \]\[\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{i*j}{(i,j)}*c_i*c_j \]\[\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{i*j}{d}*c_i*c_j*[(i,j)=d] \]\[\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}i*j*c_{id}*c_{jd}*[(i,j)=1] \]\[\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}i*j*c_{id}*c_{jd}*\sum_{k|(i,j)}\mu(k) \]\[\sum_{d=1}^{n}d\sum_{k=1}^{\frac{n}{d}}\mu(k)*k^2*\sum_{i=1}^{\frac{n}{dk}}\sum_{j=1}^{\frac{n}{dk}}i*j*c_{idk}*c_{jdk} \]设 \(T=dk\) 枚举 T
\[\sum_{T=1}^{n}T\sum_{k|T}\mu(k)*k*(\sum_{i=1}^{\frac{n}{T}}c_{iT}*i)^2 \]因为枚举 dk,而 k 是必须枚举的，所以可以省略掉 d。然后原来有 \(\sum_{d=1}^{n}d\),可以从后面找个 k 组成 T。
考虑枚举的是 \(T=dk\),所以一定有 \(k|T\).
最后预处理出 \(\sum_{k|T}\mu(k)*k\)，暴力做\((\sum_{i=1}^{\frac{n}{T}}c_{iT}*i)^2\).
因为 \(\sum_{i=1}^{n}\frac{n}{i}\) 这样子是个调和级数的形式，所以后面暴力是 \(O(n \ln n)\)的。
\(\text{Code}\)
#include
#include
#include
#include
#define N (int)(5e4+5)
#define int long long
using namespace std;
bool vis[N];
int pri[N],mu[N],sum[N],cnt;
int n,a[N],c[N];
int rd() {
int f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)) {
sum=(sum<<3)+(sum<<1)+ch-'0';
ch=getchar();
}
return sum*f;
}
void pr(int x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>9) pr(x/10);
putchar(x%10+'0');
}
void get_mu() {
mu[1]=1;
for(int i=2;i<=N-5;i++) {
if(!vis[i]) {
mu[i]=-1;
pri[++cnt]=i;
}
for(int j=1;j<=cnt&&pri[j]*i<=N-5;j++) {
vis[pri[j]*i]=1;
if(i%pri[j]==0) break;
mu[pri[j]*i]=-mu[i];
}
}
}
signed main() {
get_mu();
n=rd(); int qwq=0;
for(int i=1;i<=n;i++) {
a[i]=rd(); qwq=max(qwq,a[i]);
++c[a[i]];
}
for(int i=1;i<=qwq;i++)
for(int j=i;j<=qwq;j+=i)
sum[j]+=mu[i]*i;
int ans=0;
for(int T=1;T<=qwq;T++) {
int ret=0;
for(int i=1;i<=qwq/T;i++) ret+=i*c[i*T];
ret*=ret;
ans+=T*ret*sum[T];
//cout< 较为困难的LCM
\[\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j) \]\[n \le 10^{10} \]那么我们没办法用 \(O(n \ln n)\) 的办法了。
先化简下
\[\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{i*j}{(i,j)} \]\[\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{i*j}{d}*[(i,j)=d] \]\[\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}i*j*[(i,j)=1] \] \[h(n)=\sum_{i=1}^{n}i*[(i,n)=1] \]这个东西就等于（实际上是我 oeis 出来的）
\[\dfrac{n*\phi(n)+[n=1]}{2} \]考虑证明下
已有 \(gcd(i,n)=1\).
若有一个数 \(d,(d\neq1)\) 使得 \(gcd(n,(n-i))=d.\)
那么 \(n\%d=0,(n-i)\%d=0\implies i\%d=0\)
那么 \(gcd(i,n)=d\).
所以可得，已有 \(gcd(i,n)=1 \implies gcd(n,(n-i))=1.\)
考虑 \(i,n-i\) 成对出现，且对答案贡献是 \(n\).
则去重后答案为 \(\dfrac{n*\phi(n)+[n=1]}{2}\).
那么
\[ans=\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}i*j*[(i,j)=1] \]\[\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}i*2*h(i)-1 \]\[\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}i*2*\dfrac{i*\phi(i)+[i=1]}{2}-1 \]\[\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}i^2*\phi(i) \]因为 \([i=1]\) 与 \(-1\) 抵消了。
\[S(n)=\sum_{i=1}^{n}i^2*\phi(i) \]那么
\[ans=\sum_{d=1}^{n}d*S(\frac{n}{d}) \] \[f(x)=x^2*\phi(x),g(x)=x^2. \]那么
\[(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=n^3 \]这里省略的可以在这里找到。
接下来就是杜教筛了。
最后整个 \(ans\) 来个整除分块。
\(\text{Code}\)
#include
#include
#include
#include
#include