P1390 sum of common divisor (Mobius inversion)

Topic link

The question ：

Given $n$, seek ${\sum }_{i=1}^n{\sum }_{j=i+1}^{n}gcd(i,j)$.$(n<=2e6)$

deduction ：

First step , Follow the routine first $gcd$ Bring it to the front ,

${\sum }_{g=1}^{n}g{\sum }_{i=1}^n{\sum }_{j=i+1}^n[g=gcd(i,j)]$

The second step , We make $f(g)={\sum }_{i=1}^n{\sum }_{j=i+1}^n[g=gcd(i,j)]$, What we ask for at this time is ${\sum }_{g=1}^{n}gf(g)$, Put it first. .

Then at this time, we choose one from the formula of Mobius inversion , Once you have experience, you will know which one to choose .
We make ,

$F(g)={\sum }_{g|d}f(d)$

$={\sum }_{g|d}{\sum }_{i=1}^n{\sum }_{j=i+1}^n[d=gcd(i,j)]$

$={\sum }_{i=1}^n{\sum }_{j=i+1}^n[g|gcd(i,j)]$

$={\sum }_{i=1}^n{\sum }_{j=i+1}^n[g|i\wedge g|j]$

$=\frac{1}{2}(\lfloor \frac{n}{g}\rfloor \lfloor \frac{n}{g}\rfloor -\lfloor \frac{n}{g}\rfloor )$

According to the inversion formula , Yes $f(g)={\sum }_{g|d}\mu (\frac{d}{g})F(d)$

So let's go back to the original formula ,

${\sum }_{g=1}^{n}gf(g)={\sum }_g^n{\sum }_{g|d}\mu (\frac{d}{g})F(d)$

Pushed ahead ,$F(d)$ Sure $o(1)$ count , Mobius function can preprocess , So the final formula can $o(nlogn)$ Come on .

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
typedef pair<int,int> P;
const ll MAXN=2000000;

ll prime[MAXN+10],notPrime[MAXN+10],mu[MAXN+10],tot;
void initMu(ll n)
{
    
    notPrime[1]=mu[1]=1;
    for(ll i=2;i<=n;i++)
    {
    
        if(!notPrime[i])prime[tot++]=i,mu[i]=-1;
        for(ll j=0;j<tot&&i*prime[j]<=n;j++)
        {
    
            notPrime[i*prime[j]]=1;
            if(i%prime[j])mu[i*prime[j]]=-mu[i];
            else {
    mu[i*prime[j]]=0;break;}
        }
    }
}

ll n;
ll getF(ll g)
{
    
    ll t=n/g;
    return (t*t-t)/2;
}

int main()
{
    
    initMu(MAXN);
    scanf("%lld",&n);
    ll ans=0;
    for(ll g=1;g<=n;g++)
    {
    
        for(ll d=g;d<=n;d+=g)
        {
    
            ans=ans+g*mu[d/g]*getF(d);
        }
    }
    printf("%lld\n",ans);
    return 0;
}