数论大学习2

· · 题解

继 Pollard-Rho 后又一次讲到了杜教筛，遂再来写一篇题解趁热打铁一下

狄利克雷卷积

对于两个数论函数 f 和 g，那么定义其狄利克雷卷积结果 h 为 h(x)=\sum_{d \mid x}f(d)g(\frac{x}{d})=\sum_{ab=x}f(a)g(b)，记为 h=f * g

狄利克雷这么定义是有他的道理，我们发现这个运算满足交换律、结合律、分配律，而且两个积性函数的狄利克雷卷积还是积性函数，均可推式子求证

还是定义：

  1. 1$: $f(x)=1
  2. \varepsilon$: 单位元，对于任意数论函数 $f$，有 $f * \varepsilon=f$，具体内容是 $\varepsilon(x)=[x=1]
  3. id^k$: 幂函数，$id^k(x)=x^k$，$k=1$ 时可省略 $k
\mu(x) &= \begin{cases} 1 & \text{if } x =0 \\ 0 & \text{if } \exists \text{ }p\in P, p^2\mid x \\ (-1)^k & \text{if }x=\prod_{i=1}^k p_i \land\forall p_i,p_i\in P\land \forall i\neq j, p_i\neq p_j \end{cases} \end{align*}
  1. \varphi$: 欧拉函数，$\varphi(x)=\sum_{i=1}^x[\gcd(i,x)=1]=x\prod_{p\in P,p|x}\frac{p-1}{p}

那么我们就可以发现：

  1. \varepsilon=\mu * 1
  2. \varphi=\mu * id
  3. id=\varphi * 1

还有很多别的常用卷积式，不过已经够了

杜教筛

定义大写字母为原函数的前缀和，例 F(x)=\sum_{i=1}^x f(x)

我们需要快速求解 F(x)，直接做很明显是劣的，于是便有了快速求解的方法——杜教筛

对于任意一个数论函数 g，令 h=f * g，则有：

H(n)&=\sum_{i=1}^n\sum_{d\mid i}g(d)f(\frac{i}{d})\\ &=\sum_{i=1}^n\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}g(i)f(j)\\ &=\sum_{i=1}^ng(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}f(j)\\ &=\sum_{i=1}^ng(i)F(\lfloor\frac{n}{i}\rfloor) \end{aligned}

进而便有：

g(1)F(n)=H(n)-\sum_{i=2}^ng(i)F(\lfloor\frac{n}{i}\rfloor)

于是如果 H(n) 和 G(n) 是好求的，便可以进行递归+根号分治求解

然而复杂度正确吗？首先可以预处理 H(n)，再线性筛掉前 m 个 F(n)，注意到这是 O(m) 的

然后再进行递归，设求 F(n) 的复杂度是 T(n) 的，则

T(n)&=O(m)+\sum_{k=2}^n [\lfloor\frac{n}{k}\rfloor>m]T(\lfloor\frac{n}{k}\rfloor)\\ &=O(m)+\sum_{k=1}^{\lfloor\frac{n}{m}\rfloor}O(\sqrt\frac{n}{k})\\ &=O(m+\int_0^{\frac{n}{m}}\sqrt{\frac{n}{x}}\mathrm{d}x)\\ &=O(m+\frac{n}{\sqrt{m}}) \end{aligned}

于是使用均值不等式，当 m=n^{\frac{2}{3}} 时，T(n)=O(n^{\frac{2}{3}})

模板代码：

int F(int n) { 
    if (n <= m) return init[n]; // 预处理
    if (mp[n]) return mp[n]; // 记忆化
    int ans = H(n);
    for (int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l); // 根号分治
        ans -= (G(r) - G(l - 1)) * F(n / l);
    }
    return mp[n] = ans / g1;
}

【模板】杜教筛

求 \sum_{i=1}^n\mu(n),\sum_{i=1}^n\varphi(n)

根据 \mu * 1=\varepsilon,\varphi * 1=id，然后套用模板代码求解即可

code:

#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std; 

const int maxn = 1e6 + 10, mod = 998244353; 
vector<int> pr;
map<int, int> mphi, mmu;
int m, iphi[maxn], imu[maxn], ntp[maxn];
int mu(int n) { // mu * 1 = epsilon
    if (n <= m) return imu[n];
    if (mmu[n]) return mmu[n];
    int ans = 1;
    for (int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans -= (r - l + 1) * mu(n / l);
    }
    return mmu[n] = ans;
}
int phi(int n) { // phi * 1 = id
    if (n <= m) return iphi[n];
    if (mphi[n]) return mphi[n];
    int ans = n * (n + 1) / 2;
    for (int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans -= (r - l + 1) * phi(n / l);
    }
    return mphi[n] = ans;
}
signed main() {
    ios::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0);
    m = 1000000; 
    ntp[1] = iphi[1] = imu[1] = 1;
    for (int i = 2; i <= m; i++) {
        if (!ntp[i]) pr.push_back(i), iphi[i] = i - 1, imu[i] = -1;
        for (int p : pr) {  
            if (i * p > m) break;
            ntp[i * p] = 1;
            if (i % p == 0) {
                iphi[i * p] = iphi[i] * p;
                break;
            }
            iphi[i * p] = iphi[i] * (p - 1);
            imu[i * p] = -imu[i];
        }
    }
    for (int i = 1; i <= m; i++) imu[i] += imu[i - 1], iphi[i] += iphi[i - 1];
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << phi(n) << " " << mu(n) << endl;
    }
    return 0; 
}

似乎能水一篇题解...