正题

题目链接:https://gmoj.net/senior/#main/show/4496

---

给出\(n\)，定义

\[f(i)=\sum_{d|i}gcd(d,\frac{i}{d})
\]

求

\[\sum_{i=1}^nf(i)
\]

\(1\leq n\leq 10^{11}\)

---

考虑枚举\(x=d\)和\(y=\frac{n}{d}\)

\[\sum_{x=1}\sum_{y=1}[xy\leq n]gcd(x,y)
\]

\[\sum_{d=1}d\sum_{x=1}\sum_{y=1}[xyd^2\leq n][gcd(x,y)=1]
\]

然后莫反

\[\sum_{d=1}d\sum_{k=1}\mu(k)\sum_{x=1}\sum_{y=1}[xyd^2k^2\leq n]
\]

\[\sum_{d=1}d\sum_{k=1}\mu(k)\sum_{x=1}\lfloor\frac{\lfloor\frac{n}{d^2k^2}\rfloor}{x}\rfloor
\]

因为要求\(k^2d^2\leq n\)所以可以考虑暴力枚举\(k\)和\(d\)，然后最后那个整除分块就好了。

这样会慢几秒，把后面那个式子每次算的时候顺便记忆化了就可以了。

---

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const ll N=316228;
ll n,ans,mu[N],pri[N/10],p1[N],p2[N],cnt,S,T;
bool v[N];map<ll,ll> mp;
void Prime(){
    mu[1]=1;
    for(ll i=2;i<N;i++){
        if(!v[i])pri[++cnt]=i,mu[i]=-1;
        for(ll j=1;j<=cnt&&i*pri[j]<N;j++){
            v[i*pri[j]]=1;
            if(i%pri[j]==0)break;
            mu[i*pri[j]]=-mu[i];
        }
    }
}
ll GetF(ll n){
    ll ans=0;
    if(n>=T&&p2[S/n])return p2[S/n];
    if(n<T&&p1[n])return p1[n];
    for(ll l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        ans+=(n/l)*(r-l+1);
    }
    if(n>=T)return p2[S/n]=ans;
    return p1[n]=ans;
}
ll GetG(ll n){
    ll ans=0;
    for(ll i=1;i*i<=n;i++)
        ans+=mu[i]*GetF(n/i/i);
    return ans;
}
signed main()
{
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    Prime();
    scanf("%lld",&n);
    T=sqrt(n);S=n;
    for(ll i=1;i*i<=n;i++)
        ans+=i*GetG(n/i/i);
    printf("%lld\n",ans);
    return 0;
}