不想咕太久..就随便找个题更一下
题意
求题面里那个式子
题解
有一个常用的小式子
$$\sum_{x|a,x|b}\varphi(x)=\gcd(a,b)$$
用这个式子直接对题面的式子进行化简
$$
\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^n(a_i,a_j)·(i,j)\\
&=\sum_{i=1}^n\sum_{j=1}^n(\sum_{x|i,x|j}\varphi(x))(a_i,a_j)\\
&=\sum_{x=1}^n\varphi(x)\sum_{x|i}\sum_{x|j}(a_i,a_j)
\end{aligned}
$$
枚举x，相当于求一个大小为$ \frac{n}{x}$的集合内两两$ \gcd$的和
再用一次最上面的式子优化
$$
\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^n\gcd(a_i,a_j)\\
&=\sum_{d=1}^n\varphi(d)(\sum_{i=1}^n[d|a_i])^2
\end{aligned}
$$
预处理每个数的约数，每次暴力计算
复杂度是对的..跑的飞快...
代码
小范围暴力抢了rk1
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x=;char zf=;char ch=getchar();
while(ch!='-'&&!isdigit(ch))ch=getchar();
if(ch=='-')zf=-,ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();return x*zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt,ans;
#define N 100000
bool pri[N+];int ss[N+],phi[N+];
void init(){
phi[]=;
for(rt i=;i<=N;i++){
if(!pri[i]) ss[++cnt]=i,phi[i]=i-;
for(rt j=;j<=cnt&&i*ss[j]<=N;j++){
phi[i*ss[j]]=phi[i]*phi[ss[j]];
pri[i*ss[j]]=;
if(i%ss[j]==){
phi[i*ss[j]]=phi[i]*ss[j];
break;
}
}
}
}
int a[],sum[];
vector<int>ys[];
ll calc2(int x){
ll ret=;
for(rt i=x;i<=n;i+=x)sum[a[i]]++;
for(rt i=;i<=n;i++){
int now=;
for(rt j=i;j<=n;j+=i)now+=sum[j];
ret+=1ll*phi[i]*now*now;
}
for(rt i=x;i<=n;i+=x)sum[a[i]]=;
return ret;
}
ll calc(int x){
ll ret=;
for(rt i=x;i<=n;i+=x){
for(auto j:ys[a[i]]){
ret+=(sum[j]*+)*phi[j];
sum[j]++;
}
}
for(rt i=x;i<=n;i+=x){
for(auto j:ys[a[i]])sum[j]=;
}
return ret;
}
int main(){
init();n=read();
for(rt i=;i<=n;i++)a[i]=read();
for(rt i=;i<=n;i++)
for(rt j=i;j<=n;j+=i)ys[j].push_back(i);
ll ans=;
for(rt x=;x<=n;x++){
if(x<=)ans+=1ll*phi[x]*calc2(x);else
ans+=1ll*phi[x]*calc(x);
}
cout<<ans%;
return ;
}