《一道思维题（小trick）》
\[ans=\sum _{i=1}^{n} \sum _{j=1}^{n}lcm(a_i,a_j) \]当然正常莫反不能是这种形式的，可以观察到 \(a_i\) 的值域很小，只有 \(5\times 10^4\) ，所以我们去考虑直接枚举。
$\quad $ 记 \(c_{a_i}\) 为 \(a_i\) 在序列中出现的个数， \(N\) 为 \(a_i\) 的最大值，那么：
\begin{aligned}
ans&=\sum _{i=1}^{N}\sum _{j=1}^{N}lcm(i,j)*c_i *c_j\\
&=\sum _{d=1}^{N}d \sum _{i=1}^{\lfloor \frac{N}{d} \rfloor}\sum _{j=1}^{\lfloor \frac{N}{d} \rfloor} c _{id} *c _{jd} * i * j \sum _{k|gcd(i,j)}\mu (k)\\
&=\sum _{d=1}^{N}d\sum _{k=1}^{\lfloor \frac{N}{d} \lfloor}\mu(k)k ^2 \sum _{i=1}^{\lfloor \frac{N}{kd} \rfloor}\sum _{j=1}^{\lfloor \frac{N}{kd}\rfloor}c _{ikd} *c _{jkd}\\
&=\sum _{T=1}^{N}T\sum _{d|T}{\mu(d) d}(\sum _{i=1}^{\lfloor\frac{N}{T}\rfloor}c _{iT})^2
\end{aligned}
$\quad $ 然后中间那部分直接筛即可，后面那个括号直接暴力统计。
点击查看代码
#define yhl 0
#include<bits/stdc++.h>
using namespace std;
#define int __int128
const int N=5e4;
int n,prime[N+10],tot,mu[N+10],cnt[N+10],f[N+10],ans;
bool vis[N+10];
int read(){
int ans=yhl;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
void print(int x){
if(x>9)print(x/10);
putchar(x%10|48);
}
void init(){
vis[1]=1;mu[1]=1;
for(int i=2;i<=N;i++){
if(!vis[i]){
prime[++tot]=i;
mu[i]=-1;
}
for(int j=1;j<=tot&&i*prime[j]<=N;j++){
vis[i*prime[j]]=1;
if(!(i%prime[j]))break;
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=N;i++){
for(int j=1;j*i<=N;j++){
f[i*j]+=i*mu[i];
}
}
}
int get(int x){
int op=N/x,ans=yhl;
for(int i=1;i<=op;i++)ans+=i*cnt[i*x];
return ans*ans;
}
signed main(){
init();
n=read();
for(int i=1;i<=n;i++){
int x=read();
cnt[x]++;
}
for(int i=1;i<=N;i++)
ans+=i*f[i]*get(i);
print(ans);
return yhl;
}
$\quad $ 这个码对于中间那部分的处理是 \(O(N ln N)\) 的，然后zcx问了我一下任意积性函数的筛法，发现确实不怎么会，《小探索了一下》，下面介绍一下。
$\quad $ 对于一个积性函数 \(f(x)\) ，我们知道：对于两个互质的整数 \(a\) 、\(b\) ，\(f(ab)=f(a)f(b)\) 。
$\quad $ 现在我们就知道了两个互质整数之积函数值的求法，然后我们还要知道 \(p \in prime\) 时，函数值的求法，这个很简单，直接代入即可，就不再介绍了。
$\quad $ 这里我们主要介绍 \(p \in prime\) 且 \(p|a\) 时 \(f(ap)\) 的求法，我们需要考虑多的这一个质数对我们的答案会有什么贡献，当然这个是要具体分析的，我拿上面那个函数举例：
\(f(x)=\sum _{d|x}d\mu(d)\)
$\quad $ 这时，一个 \(d\) 对该函数值有贡献，当且仅当 \(\mu(d)\) 不为零，思考一下我们发现，多了一个质数 \(p\)，但是可以产生贡献的 \(d\) 实际上是没有发生变化的，后面的部分也不会发生变化。所以这个质数 \(p\) 此时没有多产生什么贡献。
$\quad $ 也就有：\(f(ap)=f(a)\) 。
然后我们就有了 \(O(n)\) 的筛法了。
点击查看代码
#define yhl 0
#include<bits/stdc++.h>
using namespace std;
#define int __int128
const int N=5e4;
int n,prime[N+10],tot,mu[N+10],cnt[N+10],f[N+10],ans;
bool vis[N+10];
int read(){
int ans=yhl;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10|48);
}
void init(){
vis[1]=1;f[1]=1;
//不要忘了f(1)=1。
for(int i=2;i<=N;i++){
if(!vis[i]){
prime[++tot]=i;
f[i]=1-i;
}
for(int j=1;j<=tot&&i*prime[j]<=N;j++){
vis[i*prime[j]]=1;
if(!(i%prime[j])){f[i*prime[j]]=f[i];break;}
f[i*prime[j]]=f[i]*f[prime[j]];
}
}
}
int get(int x){
int op=N/x,ans=yhl;
for(int i=1;i<=op;i++)ans+=i*cnt[i*x];
return ans*ans;
}
signed main(){
init();
n=read();
for(int i=1;i<=n;i++){
int x=read();
cnt[x]++;
}
for(int i=1;i<=N;i++)
ans+=i*f[i]*get(i);
print(ans);
return yhl;
}