重要引理

\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\right\rfloor

数论分块

洛谷P1403

题目大意：

设f(x)为x的约数个数，求\sum_{i=1}^{n}f(i)

分析：

枚举约数i。从1～n中，含有约数i的数的个数为\left\lfloor\frac{n}{i}\right\rfloor，因此

ans=\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor

但我们发现有许多\left\lfloor\frac{n}{i}\right\rfloor是重复的。设j=\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}，即有j个数使得\left\lfloor\frac{n}{i}\right\rfloor\leq\left\lfloor\frac{n}{j}\right\rfloor，因此对于每个\left\lfloor\frac{n}{i}\right\rfloor有(j-i+1)个重复项。

int main() {
    scanf("%d", &n);
    for(int i = 1, j; i <= n; i = j+1) {
        j = n / (n/i);
        ans += (n/i) * (j-i+1);
    }
    printf("%d\n", ans);
    return 0;
}

双重数论分块：

求解形如：

\sum_{d=1}^{n}f(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor)

int main() {
    for(int l = 1, r; l <= n; l = r+1) {
        r = min(n/(n/l), m/(m/l));
        // insert your code here...
    }
    return 0;
}

积性函数

定义：若 gcd(x,y)=1 且 f(xy)=f(x)f(y)，则 f(n) 为积性函数。

完全积性函数：不要求 gcd(x,y)=1。

性质：若f(x)和g(x)均为积性函数，则以下函数也为积性函数：

\begin{aligned}
h(x)&=f(x^p)\cr h(x)&=f^p(x)\cr h(x)&=f(x)g(x)\cr h(x)&=\sum_{d|x}f(d)g(\frac{x}{d})
\end{aligned}

例子：

• 单位函数：\varepsilon(n)=[n=1]
• 恒等函数：\operatorname{id}(n)=n
• 除数函数：\sigma_{k}(n)=\sum_{d\mid n}d^k
  其中\sigma_{0}(n)=d(n)为约数个数函数，\sigma_{0}(n)=\sigma(n)为除数函数
• 常数函数：I(n)=1
• 欧拉函数：\varphi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1]
• 莫比乌斯函数（此处省略）

狄利克雷卷积

定义：两个数论函数 f 和 g 的狄利克雷卷积：

(f * g)(n) = \sum_{d \mid n} f(d) g(\frac{n}{d})

性质：
– \varepsilon 为单位元即 \varepsilon * f=f；
– 卷积具有结合律：(a * b) * c=a * (b * c).

例子：

\begin{aligned}
\varepsilon=\mu * I&\iff\varepsilon(n)=\sum_{d|n}\mu(d)\cr
\varphi * I = id &\iff\sum_{d|n}\varphi(d)=n\cr
\mu * id = \varphi&\iff\sum_{d|n}d\cdot\mu(\frac{n}{d})=\varphi(n)
\end{aligned}

欧拉函数

定义与性质

定义：

\varphi(n) 表示小于等于 n 且和 n 互质的数的个数。当 n 是质数时，显然 \varphi(n)=n-1。

性质：

• 设：n=p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}，则：\varphi(n)=n * \prod_{i=1}^{s}\frac{p_i-1}{p_i}
• $\varphi({p}^{k})=p^k-p^{k-1},p\in{prime}$
• $m=\sum_{d|m}\varphi(d)$，即 $\varphi(d_1)+\varphi(d_2)+…+\varphi(m)=m,d|m$

求单个欧拉函数

// 过程类似分解质因数
int phi(int x) {
    int ans = x;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            ans = ans / i * (i-1);
            while (x % i == 0) x /= i;
        }
    }
    if(x > 1) ans = ans / x * (x-1);
    return ans;
}

线性筛欧拉函数

int phi[N], prime[N], num[N], tot;
void init() {
    phi[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!num[i]) {
            prime[++tot] = i;
            phi[i] = i - 1;
        }
        for (int j = 1, x; j <= tot && (x = i * prime[j]) < N; j++) {
            num[x] = 1;
            if (i % prime[j] == 0) {
                phi[x] = phi[i] * prime[j];
                break;
            }
            phi[x] = phi[i] * phi[prime[j]];
        }
    }
}

莫比乌斯函数

定义与性质

定义：

\mu(x)=
\begin{cases}
1& {x=1}\cr
(-1)^k&{x=p_1p_2…p_k}\cr
0&\text{other cases}
\end{cases}

性质：

\sum_{d|x}\mu(d)=
\begin{cases}
1& {x=1}\cr
0&{x>1}
\end{cases}

即 \sum_{d|n}\mu(d)=\mu(n) * I(n)=\varepsilon(n)

从通俗上讲：
– 莫比乌斯函数μ(n)的定义域是正整数
– μ(1)=1
– 当n存在平方因子时，μ(n)=0
– 当n是素数或奇数个不同素数之积时，μ(n)=-1
– 当n是偶数个不同素数之积时，μ(n)=1

线性筛莫比乌斯函数

int prime[N], num[N], mu[N], tot;
void getmu() {
    mu[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!num[i]) {// 质数的莫比乌斯函数都是-1
            prime[++tot] = i;
            mu[i] = -1;
        }
        for (int j = 1, x; j <= tot && (x = i * prime[j]) < N; j++) {
            num[x] = 1;
            if (i % prime[j]) mu[x] = -mu[i]; // i中不含有约数prime[j]，质约数个数+1
            else break; // 出现平方因子即为0
        }
    }
}