杜教筛Powerful Number_算法

杜教筛

推导过程

设现在要求积性函数 $f(x)$ 的前缀和 $S(x)$。

用取整函数 $[x]$ 表示下取整 $\lfloor x\rfloor$，太懒了。

我们再构造一个函数 $g$（不需要积性），考虑 $f*g$ 的前缀和：

$$\begin{aligned}\sum_{i=1}^n(f*g)(i)&=\sum_{i=1}^n\sum_{d\mid i}f\left(\frac id\right)g(d)\\&=\sum_{d=1}^n\sum_{i=1}^{[\frac n d]}f(i)g(d)\\&=\sum_{d=1}^ng(d)S\left(\left[\frac n d\right]\right)\end{aligned}$$

观察得：

$$\begin{aligned} g(1)S(n)&=\sum_{i=1}^ng(i)S\left(\left[\frac n i\right]\right)-\sum_{i=2}^ng(i)S\left(\left[\frac n i\right]\right) \\&=(f*g)(n)-\sum_{i=2}^ng(i)S\left(\left[\frac n i\right]\right) \end{aligned}$$

由于第一项本身是有一个 $S(n)$ 的，现在我们利用上面的构造把 $S(n)$ 去掉后，后面的一项就只需要我们求出 $\sqrt n$ 项 $S$ 的值即可。

$$S(n)=\frac{(f*g)(n)-\sum_{i=2}^ng(i)S([\frac{n}{i}])}{g(1)}$$

$g$ 为积性函数时 $g(1)=1$：

$$S(n)=(f*g)(n)-\sum_{i=2}^ng(i)S\left(\left[\frac n i\right]\right)$$

所以杜教筛把难点规约到了一个点：

• 找到 $g$ 使得 $g$ 和 $f*g$ 的前缀和易求。

不会分析复杂度，但可以证明：预处理 $\Theta(n^{\frac 2 3})$ 项时，复杂度为 $\Theta(n^{\frac 2 3})$。

P4213 【模板】杜教筛

$T$ 次求 $\sum_{i=1}^n\varphi(i)$ 和 $\sum_{i=1}^n\mu(i)$。

$T\le 10,n\le2^{31}$。

$$\mu*I=\epsilon,\varphi*I=id$$

auto DJ=[](auto &&DJ,ll n,auto &mp,auto &&Sf,auto &&Sg,auto &&S)->ll{
    if(n<=B) return Sf[n];
    if(mp.count(n)) return mp[n];
    ll &ans=mp[n]=S(n);
    for(ll l=2,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans-=(Sg(r)-Sg(l-1))*DJ(DJ,n/l,mp,Sf,Sg,S);
    } return ans;
};
main:
    printf("%lld %lld\n",
            DJ(DJ,n,mp_phi,phi,[](ll n){return n;},[](ll n){return n*(n+1)/2;}),
            DJ(DJ,n,mp_mu,mu,[](ll n){return n;},[](ll n){return 1;})
        );

P3768 简单的数学题

求：

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

$n\le 10^{10}$。

略去复杂的莫反过程，我们要快速求 $\sum_{x=1}^nx^2\varphi(x)$，设 $f(x)=x^2\varphi(x)$。

有意思的一点是：$id^cg*id^c=id^c(g*I)$。

$$\begin{aligned} \\\sum_{d|x}d^cg(d)\left(\frac{x}{d}\right)^c=x^c\sum_{d|x}g(d)I\left(\frac x d\right) \end{aligned}$$

利用这个技巧，我们构造 $g(x)=x^2$，则 $f*g=id^2(\varphi*I)=id^3$。

推导过程略去，$\sum_{x=1}^n x^3=\frac{n^2(n+1)^2}{4}$。

考场上急需自然数幂和的公式实在不行就打个高斯消元。

注：整除分块套杜教筛跑 $10^{10}$ 是没有任何问题的，因为杜教筛会计算 $n,[\frac n 2],[\frac n 3],\cdots$，所以整除分块其实只是在查表而已。

同理，这告诉我们，杜教筛套杜教筛（即 $\sum f*g$ 与 $\sum g$ 也使用杜教筛来算）是复杂度不变的！

所以建议任何情况下使用杜教筛都用哈希表记录计算过的值。

补一下反演过程：利用欧拉反演我们知道 $\sum_{d|x}\varphi(d)=x$，还有一个冷知识是 $\sum_{i=1}^ni^3=(\sum_{i=1}^ni)^2=\frac{n^2(n+1)^2}{4}$。

$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^nij(i,j)\\=&\sum_{i=1}^n\sum_{j=1}^nij\sum_{k|(i,j)}\varphi(k)\\=&\sum_{k=1}^nk^2\varphi(k)\sum_{i=1}^{n/k}i\sum_{j=1}^{n/k}j\\=&\sum_{k=1}^nk^2\varphi(k)\left(\frac{(n/k)(n/k+1)}{2}\right)^2\end{aligned}$$

到这一步已经能算了，你喜欢的话也可以接着用那个冷知识再化一步。

Powerful Number 筛

通常简记为 $\text{PN}$ 筛，是杜教筛的一种扩展。

$\text{Powerful Number}$：每个质因子的幂次都 $\ge 2$ 的数，我喜欢把其构成的集合记作 $\mathbb{PN}$（懒得打）。

性质：$|\mathbb{PN}\cap[1,n]|=\mathcal O(\sqrt n)$。

显然 $x=a^2b^3\iff x\in\mathbb{PN}$，考虑把每个奇数次质因子扔三个到 $b$ 里，剩下的和偶数次的扔到 $a$ 里，枚举 $a$ 可得：

$$\begin{aligned}&\mathcal O\left(\sum_{a=1}^{\sqrt n}\left(\frac n{a^2}\right)^{\frac 1 3}\right)\\&=\mathcal O\left(\int_1^{\sqrt n}\left(\frac n{x^2}\right)^{\frac 1 3}dx\right)\\&=\mathcal O(\sqrt n)\\\end{aligned}$$

求出 $\mathbb{PN}\cap[1,n]$ 只需要暴力搜索质因数组合即可。

设我们要求前缀和的积性函数是 $f(x)$，我们构造两个积性（狄利克雷卷积关于积性函数是封闭的）函数 $g,h$ 满足 $f=g*h$，且满足以下条件：

• $\forall p\in\mathbb P,f(p)=g(p)$。

那么由于 $\forall p\in\mathbb P,f(p)=g(p)h(1)+g(1)h(p)$，可得 $h(1)=1,h(p)=0$。

由于 $h$ 是积性函数，所以只有在 $x\in\mathbb{PN}$ 处 $h(x)$ 有可能不为 $0$。

记 $F(x)=\sum_{i=1}^xf(i),G(x)=\sum_{i=1}^x g(i)$，则：

$$\begin{aligned}F(n)&=\sum_{i=1}^n(g*h)(i)\\&=\sum_{ij\le n}g(j)h(i)\\&=\sum_{i=1}^nh(i)\sum_{j=1}^{[\frac n i]}g(i)\\&=\sum_{i\in[1,n]\cap\mathbb{PN}}h(i)G\left(\left[\frac n i\right]\right)\end{aligned}$$

放下 $G([\frac n i])$ 不管，我们还需要求出 $h(x\in\mathbb{PN})$。

由于积性函数，其实质就是要求 $h(p^k),p\in\mathbb P$。

外层枚举是 $\Theta(\sqrt n)$ 的，里面的 $G$ 根据杜教筛特性只需求一次，$\Theta(n^{\frac 2 3})$，我们就求出了这种积性函数的前缀和。

特别的，若 $G$ 容易计算，则该算法复杂度为 $\Theta(\sqrt n)$。

$G$ 不容易计算时使用杜教筛，由于我们要用到的是其块筛，所以时间复杂度就是 $\Theta(n^{2/3})$。