brz的函数题解

代码：

#include <algorithm>
#include <cstdio>

using namespace std ;

typedef long long LL ;
const int N=1e5+10 ;

int prm[N] , chk[N] , mu[N] , cnt ;
LL f[N] , g[N] ;
inline void init ( int n )
{
    int i , j ;
    mu[1]=1;
    for ( i=2 ; i<=n ; i++ )
    {
        if ( !chk[i] ) prm[++cnt]=i,mu[i]=-1;
        for ( j=1 ; j<=cnt && i*prm[j]<=n ; j++ )
        {
            chk[i*prm[j]]=1;
            if ( i%prm[j]==0 ) break;
            else mu[i*prm[j]]=-mu[i];
        }
    }
    for ( i=1 ; i<=n ; i++ )
    {
        f[i]=f[i-1];
        for ( j=1 ; j*j<=i ; j++ )
            if ( i%j==0 )
            {
                f[i]+=mu[j]*(mu[i]*mu[i]+2*mu[i]*g[j]);
                if ( j*j!=i )
                    f[i]+=mu[i/j]*(mu[i]*mu[i]+2*mu[i]*g[i/j]);
                g[j]+=mu[i];
                if ( j*j!=i )
                    g[i/j]+=mu[i];
            }
    }
    return ;
}

int main ()
{
    int T , n ;
    scanf("%d",&T),init(50000);
    while ( T-- )
        scanf("%d",&n),
        printf("%lld\n",f[n]);
    return 0 ;
}