牛客多校第六场 D 题题解

Fourier and Theory for the Universe

https://ac.nowcoder.com/acm/contest/33191/D

D Fourier and Theory for the Universe

D 题题意：记一个整数 $N$ 是好的，当且仅当 $\displaystyle N=\prod_{i=1}^k p_i^{\alpha_i}$ 中 $\sum \alpha_i$ 为偶数，且 $\forall j \in [1,k]$ ， $2\alpha_j \leq \sum \alpha_i$ 。求 $[1, n]$ 区间中有多少个好整数。 $n \leq 1\times 10^{11}$ 。

解法：在做这道题之前，先需要了解一下 min_25 筛的基本原理和流程。

min_25 筛是用于计算积性函数 $f (x)$ 的前缀和，时间复杂度为 $\dfrac{\mathcal O(n^{\frac{3}{4}})}{\log n}$ ，其使用条件： $f (x)$ 为一积性函数，满足 $f (p)$ 为一多项式函数，且 $f (p^{c})$ 可以以较低时间复杂度求出，基本思想为首先计算出小于等于 $n$ 的所有质数的 $f (x)$ 的和，然后逐步从大到小的插入质数。

整体分为两步递推：第一步为计算质数处的信息，第二步是利用质数处信息计算真正的 $f (x)$ 和。令 $K$ 为小于等于 $\sqrt n$ 的质数个数。

质数处 $f (x)$ 递推得到 $g (n, k)$

为了简单起见，令

f_1(x)= \begin{cases}f(x),x \in \Bbb P\\ \displaystyle \prod_{i=1}^kf_1^{\alpha_i}(p_i),x=\prod_{i=1}^k p_i^{\alpha_i} \cap x \not \in \Bbb P\\ \end{cases}

为一完全积性函数。通常在实际操作过程中，利用 $f (x)$ 为一多项式函数这一条件，可以令这一 $f_{1} (x)$ 为一单项式 $x^{m}$ ，对每个单项式进行单独计算再合并。设 $l_{n}$ 为合数 $n$ 的最小质因子， $p_{k}$ 为从小到大的第 $k$ 个质数， $\Bbb P$ 为质数集合，构造函数 $\displaystyle g(n,k)=\sum_{i=1}^n [i \in {\Bbb P} \cup l_i > p_k]i^m$ 。注意 $g (n, k)$ 不包含 $1$ 。 $g (n, k)$ 这一函数可以从 $k = 0$ 从小到大的递推到 $K$ ，其中 $g (n, 0)$ 为全部整数的信息，可以利用自然数幂和 $O (1)$ 的求出，而 $g (n, K)$ 则是我们想要的全体质数处的 $f (x)$ 和（因为这部分数字 $f_{1} (x) = f (x)$ ）。

考虑从 $k = j$ 转移到 $k = j + 1$ ：

g(n,j+1)\leftarrow g(n,j)-f_1(p_{j+1})\left(g\left(\left \lfloor \dfrac{n}{p_{j+1}}\right \rfloor,j\right)-g(p_{j+1},j)\right)

显然从 $k = j$ 提升到 $k = j + 1$ ，需要筛除 $l_i=p_{j+1}$ 的所有合数 $i$ 对答案的贡献。对于 $[1, n]$ 范围内满足 $l_i=p_{j+1}$ 的合数 $i$ ，有 $\dfrac{i}{p_{j+1}}$ 的最小质因子大于等于 $p_{j+1}$ 。因而问题转化到了 $\left[1,\left \lfloor \dfrac{n}{p_{j+1}}\right \rfloor\right]$ 的子问题上，因而容斥的第一项为 $g\left(\left \lfloor \dfrac{n}{p_{j+1}}\right \rfloor,j\right)$ 。但是问题是我们 $g (n, k)$ 中保留了小于等于 $p_{j+1}$ 的质数，但它们不属于要筛除的部分——这些小质数乘以 $p_{j+1}$ 构成的合数的 $l$ 值小于等于 $p_{j+1}$ ，因而对于原本的式子是不需要减掉的。然后注意到现在的 $f_{1} (x)$ 为一完全积性函数， $\dfrac{n}{p_{j+1}}$ 与 $p_{j+1}$ 不互质也是可以直接拆分的，因而质数 $p_{j+1}$ 对这部分合数的贡献可以一口气拆出来。对于形如 $\displaystyle p_{j+1}^e\prod_{k=j+2}^K p_k^{\alpha_k},e \geq 2$ 的数字，在这一步中只拆出一个 $p_{j+1}$ ，更多的 $p_{j+1}$ 在子问题的递归中逐步除去。因而有上述递推式。

但是有一个问题——对于每一个 $n$ 都需要 $n$ 与 $\left \lfloor \dfrac{n}{p_j}\right \rfloor$ 进行二元递推，因而会得到大量的形如 $\left \lfloor\dfrac{\left \lfloor \frac{n}{p_i}\right \rfloor}{p_j} \right \rfloor$ 的上界。而 $\left \lfloor\dfrac{\left \lfloor \frac{n}{p_i}\right \rfloor}{p_j} \right \rfloor =\left \lfloor\dfrac{n}{p_ip_j} \right \rfloor$ ，那么总的会需要 $O\left(\sqrt n \right)$ 个形如 $\left \lfloor \dfrac{n}{\prod p_i^{\alpha_i}}\right \rfloor$ 的上限（由整除分块可得，第一个变量至多有 $O(\sqrt n)$ 种取值， $n$ 为带求值域）需要求出。但是观察上式可以发现，只有当 $\left \lfloor \dfrac{n}{p_{j}} \right \rfloor>p_j$ 即 $p_{j}^{2} < n$ 时才会有二元递推，否则就是直接继承，因而只对 $p_{j}^{2} < n$ 的进行递推，复杂度才不是 $O\left (\sqrt n \dfrac{\sqrt n}{\log \sqrt n}\right )$ 而是 $\dfrac{\mathcal O(n^{\frac{3}{4}})}{\log n}$ 。

利用 $g (n, k)$ 得到真正的 $\sum f(x)$

设 $\displaystyle S(n,k)=\sum_{i=1}^n [l_i >p_k]f(i)$ （注意 $S (1, k) = 0$ ，不会计入 $1$ ）。同时利用线性筛计算出质数处 $\displaystyle P_j=\sum_{i=1}^jf(p_i)$ 的和。本递推由 $k = K$ 向 $k = 0$ 递推， $S (n, 0)$ 即为答案。本步递推相当“暴力”：暴力枚举本步的质数和指数。

S(n,j)= \begin{cases} g(n,K),j=K\\ \displaystyle g(n,K)-P_j+\sum_{k=j}^{K} \sum_{e=1}^{+\infty} f(p_k^e)\left(S\left(\left \lfloor \dfrac{n}{p_k^e}\right \rfloor,j+1 \right)+[e>1]\right),j<K \end{cases}

即由于 $f (x)$ 没有完全积性，因而必须枚举出 $p_{k}$ 的具体次数 $e$ ，一口气将其从 $l_i \geq p_k$ 的合数中拆出。上式的 $j < K$ 的计算分为两部分：质数处和 $l_{i} = p_{k}$ 的合数处。 $g (n, K) - P_{j}$ 为质数的计算。对于求和式内部，对于形如 $p_{k}^{e}$ 的数字，它们是要计入的，但是 $S\left(\left \lfloor \dfrac{n}{p_k^e}\right \rfloor,j+1 \right )$ 中没有算，因为它们在这部分被当作了 $1$ ；而 $e = 1$ 即 $p_{k}$ 这一数字，已经在 $g (n, K) - P_{j}$ 中计算过了，因而在后面的求和式中不能重复计算。在实际的操作中，会对 $e = 1$ 进行单独的讨论。

注意：该步不需要记忆化也可以保证正确的复杂度。

回到本题。设 $f (n, k, m, s)$ 为小于等于 $n$ 的数字， $l_{i} > p_{k}$ ，且质因数拆分中指数最大次方为 $m$ ，指数和为 $s$ 的数字个数，那么利用上述的递推可以得到：

f(n,k,m,s)={\rm Suc}(\max(m,1),s+1)(K-k)+\sum_{j=k+1}^K\sum_{e=1}^{+\infty} f\left(\left\lfloor \dfrac{n}{p_j^e}\right \rfloor,j,\max(m,e),s+e\right)+[e>1 \cap {\rm Suc}(\max(m,e),s+e)]

其中 ${\rm Suc}(m,s)$ 表示质因数拆分中指数最大次方为 $m$ ，指数和为 $s$ 的指数状态是否合法，函数值仅为 $0, 1$ ，递推思路和 $S (n, k)$ 完全相同。注意 min_25 筛中无记忆化操作，因而本题只需要利用 min_25 筛计算质数个数的时候，最后进行 $S$ 递推时，多传递几个参数即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
int tot, cnt;
long long block[N + 5];
int ind1[N + 5], ind2[N + 5];
bool vis[N + 5];
long long prime[N + 5];
long long g[N + 5], n;
int get_id(long long x)
{
    if (x <= N)
        return ind1[x];
    else
        return ind2[n / x];
}
void sieve(int n)
{
    for (int i = 2; i <= n;i++)
    {
        if(!vis[i])
            prime[++tot] = i;
        for (int j = 1; j <= tot && prime[j] * i <= n;j++)
        {
            int num = prime[j] * i;
            vis[num] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}
bool check(int maxtimes, int sumtimes)
{
    return sumtimes % 2 == 0 && maxtimes <= sumtimes / 2;
}
long long dfs(long long up, int prime_cnt, int maxtimes, int sumtimes)
{
    if(up <= prime[prime_cnt])
        return 0;
    long long ans = 0;
    if (check(max(maxtimes, 1), sumtimes + 1))
        ans += g[get_id(up)] - prime_cnt;
    for (int i = prime_cnt + 1; i <= tot && prime[i] * prime[i] <= up; i++)
    {
        long long th = prime[i];
        for (int j = 1; th <= up; th *= prime[i], j++)
        {
            ans += dfs(up / th, i, max(maxtimes, j), sumtimes + j);
            if (j > 1 && check(max(j, maxtimes), sumtimes + j))
                ans++;
        }
    }
    return ans;
}
int main()
{
    scanf("%lld", &n);
    sieve(N);
    for (long long l = 1, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        block[++cnt] = n / l;
        g[cnt] = n / l - 1;
        if (block[cnt] <= N)
            ind1[block[cnt]] = cnt;
        else
            ind2[n / block[cnt]] = cnt;
    }
    for (int i = 1; i <= tot && prime[i] <= n; i++)
        for (int j = 1; j <= cnt && prime[i] * prime[i] <= block[j]; j++)
            g[j] -= g[get_id(block[j] / prime[i])] - (i - 1); //因为每次都是前面的数字要用后面的转移，所以不会覆盖，原理同背包
    printf("%lld", dfs(n, 0, 0, 0));
    return 0;
}