P9238 [蓝桥杯 2023 省 A] 翻转硬币 - 题解

· · 题解

首先可以发现，我们可以从 1 到 n 枚举位置，如果该位上的硬币朝下，则将该硬币连同其倍数位置的硬币全部翻转。这样做是 \mathcal{O}(n \log n) 的。

记 f(i) 表示递推过程中考虑到硬币 i 时它是否需要被翻转（下文所有的 f(i) 都是模 2 意义下的），容易得到 f(i) = \sum \limits_{d | i, d \neq i} f(d)。

显然硬币 1 一定会被翻转，因此 f(1) = 1。我们最终要求的其实就是 f 函数的前缀和。

因为除硬币 1 外，所有硬币最初就是朝上的，因此 \sum \limits_{d | i} f(d) = \epsilon(i)。写作 Dirichlet 卷积形式就是 1 * f = \epsilon，反演一下得 f = \epsilon * \mu = \mu。由定义，若 f(i) = \mu(i) = -1 时，令 f(i) \gets 1 即可等效。至此问题化归为，求

\sum \limits_{i = 1} ^ n \mu^2(i)

联系 \mu^2(i) 的实际意义，我们知道该值表示 i 是否含有平方因子（\text{e.g. }\mu^2(i) = 1 表示 i 不具有平方因子）。直接枚举这些平方因子，并再对 \epsilon 作一次反演可以得到

\mu^2(i) = \sum_{d^2|i} \mu(d)

当然，换一种更加具体的理解方式，考虑对 i 唯一分解得 i = \prod p_i ^{k_i}，并令 P = \prod p_i ^{ \lfloor \frac{k_i}{2} \rfloor}，则 i 不含平方因子等价于 P = 1，因此有 \mu^2(i) = \epsilon(P) = \sum \limits_{d | P} \mu(d)，可以证明此式和上式是等价的。

由此结论，考虑每个完全平方数对答案的贡献，可以推得 \sum \limits_{i = 1} ^ n \mu^2(i) = \sum \limits_{i = 1} ^ {\sqrt n} \mu(i)\lfloor \frac{n}{i ^ 2} \rfloor，利用预处理 + 杜教筛可以求 \sum \mu(i)，对后面的 \lfloor \frac{n}{i^2} \rfloor 整除分块即可。高次整除分块的形式是 r \gets \lfloor \sqrt{\lfloor\frac{n}{\lfloor \frac{n}{l^2} \rfloor}\rfloor} \rfloor。

略提一下时间复杂度分析。

首先 \lfloor \frac{n}{i ^ 2} \rfloor 会有 \mathcal{O}(n ^ {\frac{1}{3}}) 种取值，证明很简单，如果 i \geq n ^ {\frac{1}{3}}，则 1 \leq \lfloor \frac{n}{i ^ 2} \rfloor \leq n ^ {\frac{1}{3}}，只有 n ^ {\frac{1}{3}} 种取值；如果 i \leq n ^ {\frac{1}{3}}，这样的 i 只会有 n ^ {\frac{1}{3}} 个，因此其对应的 \lfloor \frac{n}{i ^ 2} \rfloor 也只有 n ^ {\frac{1}{3}} 个。

由这个证明可以推得整除分块的“分界点”（即 r 的可能取值）近似为 1, 2, \dots, n ^ {\frac{1}{3}}, \sqrt{\lfloor \frac{n}{n ^ {\frac{1}{3}}}\rfloor}, \sqrt{\lfloor \frac{n}{n ^ {\frac{1}{3}} - 1}\rfloor}, \dots, \sqrt{\lfloor \frac{n}{1} \rfloor}，因为如果存在 i 使得 \lfloor \frac{n}{i ^ 2} \rfloor = x，则一定有一个解为 i = \sqrt{\lfloor \frac{n}{x}\rfloor}。但是在 1 \leq x \leq n ^ {\frac{1}{3}} 的枚举过程中，可能根本不存在一个 i 使得 \lfloor \frac{n}{i ^ 2} \rfloor = x，这就会产生增解。考虑到增解的数量很少，因此将其近似地忽略掉。

仿照杜教筛时间复杂度的证明过程，考虑预处理 [1, n ^ {c}](c > \frac{1}{3}) 内的 \mu 函数前缀和，需要杜教筛的部分缩小为 \sqrt{\lfloor \frac{n}{n ^ {1 - 2c}}\rfloor}, \dots, \sqrt{\lfloor \frac{n}{1}\rfloor}。为了便于计算复杂度，这里将其近似看作 {\lfloor \frac{\sqrt n}{n ^ {\frac{1}{2} - c}}\rfloor}, \dots, {\lfloor \frac{\sqrt n}{1}\rfloor}（仅仅是数值相近，而非二者真的等价）。从这里可以知道杜教筛次数的上界为 \mathcal{O}(n ^ {\frac{1}{2} - c})，每次筛的复杂度为

\mathcal{O}(\sum \limits_{i = 1} ^ {n ^ {\frac{1}{2} - c}} \sqrt{\lfloor \frac{\sqrt n}{ i} \rfloor}) = \mathcal{O}(\int_{1} ^ {n ^ {\frac{1}{2} - c}} \sqrt{\frac{\sqrt n}{x}} dx)

这一步是积分近似，解这个积分得

F(x) = 2n ^ {\frac{1}{4}}x ^{\frac{1}{2}}

将 x = n ^ {\frac{1}{2} - c} 代入，得 2n^{\frac{1}{2} - \frac{1}{2}c}，因此每次杜教筛的复杂度是 \mathcal{O}(n ^ {\frac{1}{2} - \frac{1}{2} c})。

综上所述，总复杂度 \mathcal{O}(n ^ c + n ^ {\frac{1}{2} - c} \cdot n ^ {\frac{1}{2} - \frac{1}{2} c}) = \mathcal{O}(n ^ c + n ^ {1 - \frac{3}{2} c})，取 c = \frac{2}{5} 时复杂度最优，为 \mathcal{O}(n ^ {\frac{2}{5}})。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr int N = 1e9 + 10, M = 1.6e7;

int lim;

vector<int> pr;
int vis[M], mu[M], S1_mu[M];

void sieve(){
    mu[1] = 1;
    for(int i = 2; i <= lim; i++){
        if(!vis[i]) pr.push_back(i), mu[i] = -1;
        for(int j = 0; j < pr.size() && pr[j] * i <= lim; j++){
            vis[pr[j] * i] = 1;
            if(i % pr[j] == 0){
                mu[pr[j] * i] = 0;
                break;
            }
            mu[pr[j] * i] = -mu[i];
        }
    }
    for(int i = 1; i < lim; i++)
        S1_mu[i] = S1_mu[i - 1] + mu[i];
}

unordered_map<int, int> S2_mu;

int S_mu(int n){
    if(n <= lim) return S1_mu[n];
    auto it = S2_mu.find(n);
    if(it != S2_mu.end()) return it->second;

    int res = 1;
    for(int l = 2, r; l <= n; l = r + 1){
        r = n / (n / l);
        res -= (r - l + 1) * S_mu(n / l);
    }
    return S2_mu[n] = res;
}

int main(){
    ios::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);

    i64 n; cin >> n;
    lim = powl(n, 2.0 / 5) + 10;

    sieve();

    i64 m = sqrtl(n);

    i64 ans = 0, pre = 0, cur;
    for(i64 l = 1, r; l <= m; l = r + 1){
        r = sqrtl(n / (n / (l * l)));
        ans += (S_mu(r) - S_mu(l - 1)) * (n / (l * l));
    }
    cout << ans << "\n";
}