LOJ #6539 奇妙数论题

不想咕太久..就随便找个题更一下

LOJ#6539

---

题意

求题面里那个式子

---

题解

有一个常用的小式子

$$\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 ;

}