积性函数

设f(n)是积性函数，假设$n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$，则$f(n)=f(p_1^{\alpha_1})f(p_2^{\alpha_2})\dots f(p_k^{\alpha_k})$

利用质因数分解求f(n)

ll get_ll(ll n) {
    ll ans = 0;
    for (int i = 2; i <= n / i; i++) {
        int cnt = 0;
        while (n % i == 0)
            cnt++, n /= i;
        ans*=f(i,cnt);//f(p,k)=f(p^k)
    }
    if (n > 1)
        ans *= f(n, 1);
    return ans;
}

利用欧拉筛求f(1),f(2),…,f(n)

    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!not_prime[i])
            p[++tot] = i, f[i] = cal_f(i, 1);
        for (int j = 1; j <= tot && i * p[j] <= n; j++) {
            not_prime[i * p[j]] = 1;
            if (i % p[j] == 0) {
                cnt[i * p[j]] = cnt[i] + 1;
                f[i*p[j]]=f[i]/cal_f(p[j],cnt[i])*cal_f(p[j],cnt[i]+1);
                brea
            }
            cnt[i * p[j]] = 1;
            f[i*p[j]]=f[i]*cal_f(p[j],1);
        }
    }
//p数组存放素数
//cnt[n]表示n的最小质因子的次数

1. μ(n)——莫比乌斯函数。

2. φ(n)——欧拉函数。表示不大于n且与n互质的正整数个数，十分常见的数论函数。用数学式子表示即：$φ(n)=∑^n_{i=1}[(n,i)=1](n,i)$表示gcd(n,i))

3. d(n)——约数个数。

4. σ(n)——约数和函数。 即n的各个约数之和。表示为：$σ(n)=∑_{d|n}d=∑^n_{d=1}[d|n]⋅d$

   完全积性函数

5. ϵ(n)——元函数。$ϵ(n)=[n=1]$

6. I(n)——恒等函数。

7. id(n)——单位函数。$id(n)=n$。

筛出u 函数

void get_mu(int n)
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]){prim[++cnt]=i;mu[i]=-1;}
        for(int j=1;j<=cnt&&prim[j]*i<=n;j++)
        {
            vis[prim[j]*i]=1;
            if(i%prim[j]==0)break;
            else mu[i*prim[j]]=-mu[i];
        }
    }
 }

μ函数有个性质 $\sum_{d|n}\mu(d)=[n=1]$

故 $[gcd(i,j)=1]=\sum_ {d∣gcd(i,j)} ​ μ(d)$