调和级数 除法分块 埃筛 线性筛

“你觉得最浪费时间的事是什么？”

“拿自己和别人比较”，鼹鼠说。

前言

已经好几次比赛遇到调和级数了，每次co老师要给我讲，我都委婉地拒绝了，然后每次一比赛就不会……终于在放假的第一天，把这个小小的知识，学习了一下。

调和级数

调和级数被叫做调和级数，是因其复杂度是调和级数。

经典应用：

求 每个数的因数和，最直接的想法是，先枚举 从 到 ，再枚举 的因子从 到 ，这样子复杂度为 ，能处理的数据范围大概是 。但如果想要 获得答案并且 ，原来的方法就没解决了。我们换个思路，不去枚举每一个数可能的因子，而是枚举每一个因子能对哪些数做贡献。也就是先枚举因子 从 到 ，再枚举该因子可以给哪些数提供贡献，也就是枚举 ，初始值为 ，上界为 ，步长为 ，代码如下。

for (int i = 1; i <= n; ++i) 
    for (int j = i; j <= n; j += i)

上面这段代码的复杂度为 根据调和级数可得该复杂度为 。

除法分块

除法分块要解决的问题与商有关。比如，我要求 的商数和或者余数和 ( )，即 。暴力做的话就是 的。

我们先来观察一个数 ：

被除数	1	2	3	4	5	6	7	8	9	10
商	10	5	3	2	2	1	1	1	1	1

其商可以划分为一段一段的，就利用这种性质，降低解决原问题方法的复杂度。

for (int r, t, l = 1; l <= n; l = r + 1) { //区间左端点
    t = n / l; // 商
    r = n / t; // 区间右端点
   	ans += (r - l + 1) * t; // 可以是其他的
}

该方法的复杂度为 ，

比如，以下三个式子的求解。

推导过程：

$$\begin{array}{l} \sum_{i = 1} ^ n n \mod i & = \sum_{i =1} ^n (n - \lfloor\frac n i \rfloor \times i) \\ & = n^2 - \sum_{i = 1} ^n (\lfloor \frac n i \rfloor \times i)\\ & = n^2 - \sum_t t \sum_{i = l} ^r i \\ & = n ^2 - \sum_t (t \times \frac{(l + r)(r - l + 1)} 2) \end{array}$$

ll ans = n * n;
for (int r, t, l = 1; l <= n; l = r + 1) {
    t = n / l;
    r = n / t;
    ans += 1ll * t * (l + r) * (r - l + 1) / 2;
}

$$\begin{array}{l} \sum_{i = 1}^n (\lfloor \frac n i \rfloor \times (n \mod i)) & =\sum_{i = 1} ^ n (\lfloor\frac n i \rfloor(n - \lfloor \frac n i \rfloor \times i)) \\ & =\sum_{i = 1} ^ n (n \lfloor \frac n i \rfloor - \lfloor \frac n i \rfloor^2 \times i)\\ & = \sum_{i = 1} ^ n (n \times \lfloor \frac n i \rfloor) - \sum_{i = 1} ^ n (\lfloor \frac n i \rfloor ^ 2 \times i ) \\ & = n \sum_{i = 1} ^ n \lfloor \frac n i \rfloor - \sum_{i = 1} ^ n (\lfloor \frac n i \rfloor ^ 2 \times i) \\ & = n \sum_t(t \times(r - l + 1)) + \sum_t (t^2 \times \frac{(l + r)(r - l + 1)} 2 ) \end{array}$$

ll ans = 0;
for (int r, t, l = 1; l <= n; l = r + 1) {
    t = n / l; r = n / t;
    ans += 1ll * n * t * (r - l + 1) + 1ll * t * t * (r + l) * (r - l + 1) / 2; 
}

其中 是 的二次和

$$\begin{array}{l} \sum_{i = 1} ^n (n \mod i) ^2 & = \sum_{i = 1} ^ n (n ^ 2 - 2 \times n \times \lfloor \frac n i \rfloor \times i + \lfloor \frac n i \rfloor ^ 2 \times i ^ 2) \\ & = n ^ 3 - 2 \times n \times \sum_{i =1} ^ n \lfloor \frac n i \rfloor i + \sum_{i = 1} ^ n \lfloor\frac n i \rfloor^2i^2 \\ & = n^3 - 2 \times n \times \sum_t (t \times \frac{(l + r)(r - l + 1)} 2) + \sum_t (t^2 \times (sum2(r) - sum2(l-1))) \end{array}$$

ll sum2(int x) {
    return (x * (x + 1) * (2 * x + 1)) / 6;
}

ll ans = n * n * n;
for (int r, t, l = 1; l <= n; l = r + 1) {
    t = n / l; r = n / t;
    ans += 2 * n * t * (l + r) * (r - l + 1) / 2 + t * t * (sum2(r) - sum2(l - 1));
}

数论函数

分类

数论函数按积性可分为 完全积性函数和积性函数。完全积性函数满足 ，积性函数满足 如果 和 互质，则 。

常见的完全积性函数有 、 、 等。常见积性函数有 欧拉函数 ，莫比乌斯函数 ，约数幂和函数族 。

欧拉函数

欧拉函数 ，为从 到 与 互质的数的个数。

标准分解 ：把 分解成若干个质数的幂次的和。即 。

若用标准分解来表示 ，则欧拉函数形式为 。

埃拉托斯特尼筛

大概就是套了一个调和级数。

比如，我现在要统计从 到 ，哪些数是质数。

暴力的想法就是枚举 从 到 ，再枚举 从 到 ，判断 是否含有 这个因子。这样子的复杂度是 。

稍微好一点的想法是枚举 的时候，上界只枚举到 ，因为约数是成对存在的，大于 的根所配对的一定小于 。这样子的复杂度是 。

但这还不够优秀，我们结合调和级数的想法来枚举因子，那么因子的倍数就一定不是质数，复杂度为 。代码如下：

bool isp[N]; // 0 表示是质数，1 表示不是质数

for (int i = 2; i <= n; ++i) // 1 要排除在外 且 1 是质数
    for (int j = 2 * i; j <= n; j += i) // 排除自己要从 2 * i 开始
        isp[j] = 1;

稍微再优化一下，枚举 的下界从 开始，为啥是对的呢？因为如果 如果 那么在这之前就已经筛掉了，所以下届可以从 开始。这样子的复杂度为 。

组合数

$${n \choose m} = {n - 1 \choose m - 1} + {n - 1 \choose m}$$

由上式可知，可以 求组合数。即 。

$${n \choose m} = \frac {n!} {m!(n - m)!} \\ A_n^m = \frac{n!}{(n - m)!}$$

根据以上式子可知，如果想求组合数或者排列数，只需要知道阶乘和阶乘的逆元。求阶乘的复杂度是 的，即 ；求阶乘的逆元，如果对每一个元素都用费马小定理，复杂度是 ，但其实可以做到 ，对于最后一个元素用费马小定理，再反过来求阶乘的逆元，这样做的复杂度是 ，即 。

洛谷P5431

给一组数列 ，求 。

#define N 5000007

ll fac[N], ifac[N];
int mod, a[N];

inline ll qpow(ll x, int p) {
    ll res = 1;
    for (; p; p >>= 1, x = 1ll * x * x % mod)
        if (p & 1) res = 1ll * res * x % mod;
    return res;
}

int main() {
    int n = rd(), p = rd(), k = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    mod = p;
    fac[0] = 1;
    for (int i = 1; i <= n; ++i)
        fac[i] = fac[i - 1] * a[i] % p;
    ifac[n] = qpow(fac[n], p - 2);
    for (int i = n - 1; i; --i) ifac[i] = ifac[i + 1] * a[i + 1] % p;
    ll ans = 0, tmp = k;
    for (int i = 1; i <= n; ++i) {ans = (ans + fac[i - 1] * ifac[i] % p * tmp % p) % p; tmp = tmp * k % p;}
    printf("%lld\n", ans);
    return 0;
}

线性筛

线性筛是一种数论筛法，用于求一个不大的数域内全部的函数值，可以筛出一定范围内的质数或任意积性函数的值。

其中”线性“的含义为 每个数字只被其最小的质因数筛出 ，并非时间复杂度。

假设求积性函数 的质数幂 复杂度为 ，则最终复杂度为 。

求 f(n)f(n) 的值时，考虑其标准分解

对标准分解的最小质因数的指数 的情况讨论。

• 是素数 ，即
• ，其中 是任意正整数，且 ，即
• ，其中 是任意正整数，且 ，即

下面对三类情况分别进行处理：

• 是素数 ，即
  往往可以利用数论函数的定义快速求出。
• ，其中 是任意正整数，且 ，即
  利用积性函数的定义，由于 ，有
  由于 , ， 和 在此前都已求出。

• ，其中 是任意正整数，且 ，即
  将 重新表示为 的形式，此时 ，有
  由于 ，， 和 在此前都已求出。

现在只需要解决如何快速求出 对应的 和 的值。

不妨设 , ，这两个函数虽然不是积性的，但依然可以按照上述思路讨论。

讨论 和 的关系：

• 是素数 ： ，
• ，且 ： ，
• ，且 ： ，

欧拉函数（）

表示，从 中，与 互质的数的个数。

#define N 100007

int mind[N], cnt[N], pw[N], prm[N], phi[N]; // 最小质因子; ; ; 保存质数; phi

int main() {
    phi[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!mind[i]) {
          mind[i] = i;
          phi[i] = i - 1;
          cnt[i] = 1; pw[i] = i;
          prm[++prm[0]] = i;
        }
        for (int j = 1, p = prm[1]; j <= prm[0]; p = prm[++j]) {
            int n = i * p;
            if (n > N) break;
            if (p == mind[i]) {
                mind[n] = p;
                cnt[n] = cnt[i] + 1;
                pw[n] = pw[i] * p;
                if (i == pw[i]) phi[n] = (p - 1) * i; // n = pw[n] = p^k
                else phi[n] = phi[i / pw[i]] * phi[pw[i] * p]; // 积性函数性质
                break;
            }
            phi[n] = phi[i] * phi[p]; // 积性函数性质
            cnt[n] = 1; mind[n] = pw[n] = p;
        }
    }
    return 0;
}

函数

表示，代表 的约数的 次幂和。
特别的， 是约数的个数， 是约数的和。

// sigma0
#define N 100007

int mind[N], cnt[N], pw[N], prm[N], sigma0[N];

int main() {
    sigma0[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!mind[i]) {
          mind[i] = i;
          sigma0[i] = 2;
          cnt[i] = 1; pw[i] = i;
          prm[++prm[0]] = i;
        }
        for (int j = 1, p = prm[1]; j <= prm[0]; p = prm[++j]) {
            int n = i * p;
            if (n > N) break;
            if (p == mind[i]) {
                mind[n] = p;
                cnt[n] = cnt[i] + 1;
                pw[n] = pw[i] * p;
                if (i == pw[i]) sigma0[n] = cnt[n] + 1; // n = pw[n] = p^k
                else sigma0[n] = sigma0[i / pw[i]] * sigma0[pw[i] * p];
                break;
            }
            sigma0[n] = sigma0[i] * sigma0[p];
            cnt[n] = 1; mind[n] = pw[n] = p;
        }
    }
    return 0;
}

// sigma1
#define N 100007

int mind[N], cnt[N], pw[N], prm[N], sigma1[N];

int main() {
    sigma1[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!mind[i]) {
          mind[i] = i;
          sigma1[i] = i + 1;
          cnt[i] = 1; pw[i] = i;
          prm[++prm[0]] = i;
        }
        for (int j = 1, p = prm[1]; j <= prm[0]; p = prm[++j]) {
            int n = i * p;
            if (n > N) break;
            if (p == mind[i]) {
                mind[n] = p;
                cnt[n] = cnt[i] + 1;
                pw[n] = pw[i] * p;
                if (i == pw[i]) sigma1[n] = (1 - n * p) / (1 - p); // n = pw[n] = p^k
                else sigma1[n] = sigma1[i / pw[i]] * sigma1[pw[i] * p];
                break;
            }
            sigma1[n] = sigma1[i] * sigma1[p];
            cnt[n] = 1; mind[n] = pw[n] = p;
        }
    }
    return 0;
}

欧拉函数相关的求和式推导

洛谷P2158

前置小知识：从 (0,0) 到 (x,y) 的整点的个数为 gcd(x,y) + 1 （包括两端点）

这道题是问，从原点（点阵的左下角）看向 的二维点阵，能看到多少个点。等价题意是：

给出一个 ，求

$$\sum_{i = 0}^{n-1} \sum_{j = 0}^{n-1} [(i,j) = 1]$$

推导过程：

$$\begin{array}{l} 原式 &= \sum_{i = 0}^{n-1}\bigg(\sum_{j=0}^{i-1}[(i,j) = 1] + [(i,i) = 1] + \sum_{j=i+1}^{n-1} [(i,j) = 1] \bigg) \\ &= \sum_{i = 0}^{n-1}\sum_{j=0}^{i-1}[(i,j) = 1] + \sum_{i = 0}^{n-1}[(i,i) = 1] + \sum_{i = 0}^{n-1}\sum_{j=i+1}^{n-1} [(i,j) = 1] \\ &= 2 \times \sum_{i = 0}^{n-1}\sum_{j = 0}^{i-1}[(i,j) = 1] +[n - 1 \ge 1] \\ &= 2 \times \sum_{i = 0}^{n-1}\bigg(\sum_{j = 1}^{i}[(i,j) = 1] + [(i,0) = 1] - [(i,i) = 1]\bigg) +[n \ge 2] \\ &= 2 \times \sum_{i = 0}^{n-1}\varphi(i) + [n \ge 2] \end{array}$$

所以可以先 求 ，再 对 维护前缀和，求得答案。综上，解决该问题的复杂度为 。

bzojP2818

给出一个 ，求

$$\sum_{i = 1}^{n} \sum_{j = 1}^{n} [(i,j)\ is\ prime]$$

先枚举 的值，式子变成

$$\begin{array}{l} 原式 &= \sum_{d\ is\ prime}^n \sum_{i = 1}^n \sum_{j = 1}^n [(i,j) = d] \\ &= \sum_{d\ is\ prime}^n \sum_{i = 1}^{\lfloor \frac n d \rfloor} \sum_{j = 1}^{\lfloor \frac n d \rfloor} [(i,j) = 1] \\ &= \sum_{d\ is\ prime}^n \sum_{i = 1}^{\lfloor \frac n d \rfloor}\bigg(\sum_{j = 1}^{i - 1} [(i,j)=1] + \sum_{j = i + 1}^{\lfloor \frac n d \rfloor} [(i,j) = 1] + [(i,i) = 1]\bigg)\\ &= \sum_{d\ is\ prime}^n \sum_{i = 1}^{\lfloor \frac n d \rfloor}\bigg(2 \times \sum_{j = 1}^{i - 1} [(i,j)=1] + [(i,i) = 1]\bigg)\\ &= \sum_{d\ is\ prime}^n \sum_{i = 1}^{\lfloor \frac n d \rfloor}\bigg(2 \times \sum_{j = 1}^{i} [(i,j)=1] - 2 \times [(i,i) = 1] + [(i,i) = 1]\bigg)\\ &= \sum_{d\ is\ prime}^n \sum_{i = 1}^{\lfloor \frac n d \rfloor}\bigg(2 \times \varphi(i) - [(i,i) = 1]\bigg)\\ &= \sum_{d\ is\ prime}^n \bigg(2\times \sum_{i = 1}^{\lfloor \frac n d \rfloor}\varphi(i) - 1\bigg) \end{array}$$

所以可以先 求 ，再 对 维护前缀和（或者对 维护前缀和），线性筛出所有质数。其中 ，因为只有当 时才成立，且 一定大于 。综上，解决该问题的复杂度为 。

洛谷P2398

给出一个 ，求

$$\sum_{i=1}^n \sum_{j=1}^n (i,j)$$

先枚举 的值，式子变成

$$\sum_{d=1}^n d \sum_{i=1}^n\sum_{j=1}^n[(i,j) = d]$$

跟上面一道题一样推导可以得到最后的式子为

$$\sum_{d=1}^n d\bigg(2\times \sum_{i = 1}^{\lfloor \frac n d \rfloor}\varphi(i) - 1\bigg)$$