[计蒜客] tsy's number 解题报告 (莫比乌斯反演+数论分块)

interlinkage:

https://nanti.jisuanke.com/t/38226

description:

solution:

显然$\frac{\phi(j^2)}{\phi(j)}=j,\frac{\phi(k^3)}{\phi(k)}=k^2$

原式可以化简为

$\sum_{i=1}^{n}\sum_{j=1}^n\sum_{k=1}^{n}jk^2\phi(gcd(i,j,k))$

我们枚举$gcd(i,j,k)$，得

$\sum_{d=1}^{n}\phi(d)\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^njk^2[gcd(i,j,k)==d]$

$\sum_{d=1}^{n}\phi(d)\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}\sum_{k=1}^{n/d}jk^2d^3[gcd(i,j,k)==1]$

$\sum_{d=1}^{n}\phi(d)\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}\sum_{k=1}^{n/d}jk^2d^3\sum_{s|gcd(i,j,k)}\mu(s)$

设$sum1(n)=\sum_{i=1}^{n}i,sum2(n)=\sum_{i=1}^{n}i^2$

$\sum_{d=1}^{n}\phi(d)\sum_{i=1}^{n/d}\mu(i) \lfloor\frac{n}{id}\rfloor sum1(\lfloor\frac{n}{id}\rfloor) sum2(\lfloor\frac{n}{id}\rfloor)i^3d^3$

枚举$id$

$\sum_{T=1}^{n}\phi*\mu(T) T^3 \lfloor\frac{n}{T}\rfloor sum1(\lfloor\frac{n}{T}\rfloor) sum2(\lfloor\frac{n}{T}\rfloor)$

显然$\phi*\mu(T) T^3$是一个积性函数，我们可以把它线性筛出来

维护一下每个数的最小质因子及其最小质因子的指数就好了

后面显然可以分块，时间复杂度为$O(N+T\sqrt{n})$

code:

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

const int N=1e7+;

const int mo=1ll<<;

int cnt;

int prime[N],num[N],mi[N],f[N],sum[N];

bool vis[N];

inline int read()

{

    char ch=getchar();int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

int qpow(int a,int b)

{

    int re=;

    for (;b;b>>=,a=a*a) if (b&) re=re*a;

    return re;

}

ll phi(int p,int k)

{

    if (!k) return ;

    return 1ll*qpow(p,k-)*(p-);

}

void pre()

{

    ll sum1=,sum2=;

    for (int i=;i<N;i++)

    {

        sum1=(sum1+i)%mo;

        sum2=(sum2+1ll*i*i%mo)%mo;

        sum[i]=sum1*sum2%mo*i%mo;

    }

    f[]=;

    for (int i=;i<N;i++)

    {

        if (!vis[i])

        {

            prime[++cnt]=i;

            mi[i]=i;num[i]=;

            f[i]=1ll*i*i%mo*i%mo*(i-)%mo;

        }

        for (int j=;j<=cnt&&prime[j]*i<N;j++)

        {

            vis[i*prime[j]]=;

            mi[i*prime[j]]=prime[j];

            if (mi[i]==prime[j]) num[i*prime[j]]=num[i]+;

            else num[i*prime[j]]=;

            if (i%prime[j]) f[i*prime[j]]=1ll*f[i]*f[prime[j]]%mo;

            else

            {

                int q=qpow(prime[j],num[i*prime[j]]);

                f[q]=1ll*(phi(prime[j],num[i*prime[j]])-phi(prime[j],num[i*prime[j]]-))*q%mo*q%mo*q%mo;

                f[i*prime[j]]=1ll*f[i*prime[j]/q]*f[q]%mo;

                break;

            }

        }

    }

    for (int i=;i<N;i++) f[i]=1ll*(f[i-]+f[i])%mo;

}

int main()

{

    pre();

    int T=read();

    while (T--)

    {

        int n=read();

        ll ans=;

        for (int l=,r;l<=n;l=r+)

        {

            r=n/(n/l);

            (ans+=1ll*(f[r]-f[l-])*sum[n/l]%mo)%mo;

        }

        printf("%lld\n",1ll*(ans+mo)%mo);

    }

    return ;

}