积性函数

当$(n,m) = 1$时有$f(nm) = f(n)f(m)$，则称$f(x)$ 为积性函数。

线性筛法

对于每一个数字$n$，用其最小的质因数筛去，考虑最小质因数 $p$ 与数字 $n$ 的三种情况

1. $n = p$ 。

2. $p|n, p<n$

3. $else$

三种情况分别考虑即可。

以欧拉函数为例：

1. $\phi (i) = i-1$

2. $\phi (tp) = \phi (t) \times p$

3. $\phi (tp) = (p-1) \times \phi(t) $ 这样可以 $O(n)$ 筛出相应函数

例：求出 1~n! 中与 m! 互质的数字个数。

x 与 m! 互质 <-> x 与 1 ~ m 互质 <-> x 不含有 ≤ m的质数。

这样考虑 $x = m!t + k$

$p | x$ <=> $p | k$，这样有 $ans = m! \prod {1 - \frac{1}{p_i}}$

应用阶乘法筛出逆元（用 $(P-1)!^{-1}$ 逆推），预处理出后一部分前缀积，复杂度 $O(n + T)$

#include <iostream>
#include <cstdio>
#include <cstring>

#define LL long long
#define N 10000010

using namespace std;

int tot, prime[N], inv[N], fac[N], P, prev[N];
bool v[N];

int mul(int a,int b)
{
    return a*(LL)b % (LL)P;
}

int qpow(int x,int n)
{
    int ans = 1;
    for(;n;n>>=1,x = mul(x, x))
        if(n&1) ans = mul(ans, x);
    return ans;
}

void init()
{
    fac[0] = 1;
    int nl = min(N,P);
    for(int i=1;i < nl ;i++) fac[i] = mul(fac[i-1], i);
    int tmp = qpow(fac[nl-1], P-2);
    for(int i=nl-1;i>=1;i--)
    {
        inv[i] = mul(tmp, fac[i-1]);
        tmp  = mul(tmp, i);
    }
}

int main()
{
    int T;
    cin>>T>>P;
    init();
    for(int i=2;i<N;i++)
    {
        if(!v[i]) prime[++tot] = i;
        for(int j=1;i*prime[j]<N;j++)
        {
            v[i*prime[j]] = 1;
            if(i%prime[j]==0) break;
        }
    }
    int j = 1;
    prev[0] = 1;
    for(int i=1;i<N;i++)
    {
        prev[i] = prev[i-1];
        if(j<=tot && prime[j]==i)
        {
            prev[i] += P - mul(prev[i] ,inv[i]);
            if(prev[i] >= P) prev[i] -= P;
            j++;
        }
    }
    int n,m;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        printf("%d\n",mul(fac[n], prev[m]));
    }
    return 0;
}

View Code

常见积性数论函数

$\mu (i)$ ：狄里克莱卷积里的逆元函数

当i为若干个不同质数相乘得到，则 $\mu (i) = (-1) ^ {cnt}$ （$cnt$ 表示i中质因数的个数）

不然 $\mu (i) = 0$

1. $\mu (i) = -1$

2. $\mu (tp) = 0$

3. $\mu (tp) = -\mu (t)$

$e (i)$ ：判别函数， [i =1]

$d (i)$ ：约数个数，建立辅助函数 $a (i)$ 表示最小质因数的指数

$d(i) = \prod {t_i + 1}, i = p_1^{t_1} p_2^{t_2} ... p_{cnt}^{t_{cnt}}$

1. $d(i) = 2, a(i) = 1$

2. $d(tp) =  \frac{d(t)}{a(t)+1} \times (a(t)+2) , a(tp) = a(t) + 1$

3. $d(tp) = 2 d(t)$

$\sigma (i)$ ：约数和

记 $F(p,t) = \frac{1 - p ^ {t + 1}}{1 - p}$

$\sigma (i) = \prod { F(p_i, t_i)  }$

1. $\sigma (i) = i+1$

2. $\sigma (tp) = \frac{\sigma (t)}{ F(p, a(t)) } \times F(p, a(t)+1)$

3. $\sigma (tp) = \sigma (t) (p+1)$

 狄里克莱卷积

首先有两个常用的性质：

$\sum _{d|n} {\phi (d)} = n, \phi \times I = id$

$\sum_{d|n} {\mu (d)} = e(n), \mu \times I = e$

如果 $f, g$ 为积性函数，则有 $f \times g, f \cdot g$ 为积性函数。

数论函数变换学习P1