Rolling Girl - 题解

标签与难度

标签: 数论, 莫比乌斯反演, 狄利克雷卷积, 欧拉函数, GCD, 算法设计难度: 2400

题目大意喵~

各位Master，miku酱被困在一个有 $N$ 个位置的魔法环里啦，位置编号从 $1$ 到 $N$ 。每个位置 $i$ 都有一个耐久度 $a_i$ 。

Miku酱会从 $N$ 号位置开始，每次向前跳跃固定的距离 $d$ 。每次降落到一个位置，那个位置的耐久度就会减少 $1$ 。当环上任意一个位置的耐久度降到 $0$ 时，魔法就会消失，miku酱就能从 $N$ 号位置逃脱啦！

这个过程会重复 $N$ 次。第 $i$ 次尝试中，跳跃的距离 $d$ 会被设定为 $i$ 。我们需要计算 miku酱在这 $N$ 次尝试中，总共需要跳跃多少次才能逃脱。每次尝试结束后，环上所有位置的耐久度都会恢复原状哦。

因为答案可能很大，所以要对 $1004535809$ 取模。还有呐，为了方便，题目给了一个数据生成器来生成 $a_i$ 数组。

解题思路分析

这道题看起来好复杂呀，要把 $N$ 次逃脱过程的总跳跃次数加起来，喵~ 但是不要怕，让我带你一步一步把问题拆解开，找到通往正确答案的路！

Step 1: 分析单次逃脱过程

首先，我们只考虑某一次逃脱，假设这次的跳跃距离是固定的 $d$ 。

Miku酱从位置 $N$ 开始跳。因为环是圆的，所有位置的计算都要在模 $N$ 的意义下进行。为了方便，我们把位置 $N$ 看作是 $0$ 或者 $N$ 。第 $t$ 次跳跃后，miku酱会落在哪个位置呢？

她从位置 $p$ 跳跃距离 $d$ ，会落在 $(p+d-1 \pmod N) + 1$ 。但更简单的看法是，如果把位置看作 $0, 1, \dots, N-1$ ，从 $N-1$ 开始跳，第 $t$ 次跳跃会落在 $(N-1+t \cdot d) \pmod N$ 。所以，miku酱能访问到的位置 $j$ 都满足一个条件： $j-1 \equiv N-1 \pmod{\gcd(d, N)}$ 。令 $g = \gcd(d, N)$ ，所有被访问到的位置 $j$ 都满足 $j \equiv 0 \pmod g$ 。也就是说，miku酱只会落在 $\{g, 2g, 3g, \dots, (N/g)g = N\}$ 这些位置上！

这些位置形成了一个小圈圈，一共有 $N/g$ 个点。miku酱会按顺序一次又一次地访问它们。

那么，需要跳多少次才能逃脱呢？逃脱的条件是任意一个位置的耐久度归零。这当然是由这个小圈圈里最脆弱的那个位置决定的啦！

假设在 $\{g, 2g, \dots, N\}$ 这些位置中，最小的耐久度是 $m_g$ 。为了让某个耐久度为 $a_j$ 的位置 $j$ 坏掉，我们需要精确地跳到它身上 $a_j$ 次。设位置 $j$ 在这个跳跃距离为 $d$ 的小圈圈里是第 $\text{rank}_d(j)$ 个被访问到的。那么要让它坏掉，总共需要跳跃 $(a_j-1) \times (\text{圈长}) + \text{rank}_d(j)$ 次。圈长就是 $N/g$ 。所以，对于一个固定的 $d$ ，总跳跃次数 $J(d)$ 就是：

J(d) = \min_{j \in \{g, 2g, \dots, N\}} \left\{ (a_j - 1) \frac{N}{g} + \text{rank}_d(j) \right\}

因为 $(a_j-1)N/g$ 这一项是主要部分，而 $\text{rank}_d(j)$ 只是 $1$ 到 $N/g$ 之间的小零头，所以拥有最小耐久度 $m_g$ 的位置肯定会是候选者。设 $K_{min,g}$ 是那些耐久度恰好为 $m_g$ 的位置的指标集合（例如，如果 $a_{2g}$ 和 $a_{5g}$ 最小，那么 $K_{min,g}=\{2, 5\}$ ）。那么公式可以简化为：

J(d) = (m_g-1)\frac{N}{g} + \min_{k \in K_{min,g}} \{ \text{rank}_d(kg) \}

Step 2: 汇总所有情况

我们的目标是计算 $\sum_{d=1}^N J(d)$ 。一个很自然的想法是，按照 $g = \gcd(d, N)$ 的值来分类计算！

\text{总跳跃次数} = \sum_{g | N} \sum_{\substack{1 \le d \le N \\ \gcd(d,N)=g}} J(d)

对于所有 $\gcd(d,N)=g$ 的 $d$ ， $(m_g-1)N/g$ 这一项是完全相同的！满足 $\gcd(d,N)=g$ 的 $d$ 的个数，正好是 $\phi(N/g)$ （欧拉函数，喵~）。所以，总和可以拆成两部分：

\text{总和} = \sum_{g|N} \phi(N/g) \cdot (m_g-1)\frac{N}{g} + \sum_{g|N} \sum_{\substack{1 \le d \le N \\ \gcd(d,N)=g}} \min_{k \in K_{min,g}}\{\text{rank}_d(kg)\}

第一部分很好算，我们预处理欧拉函数 $\phi$ ，然后遍历 $N$ 的所有约数 $g$ 就可以啦。

Step 3: 处理棘手的第二部分

第二部分是真正的挑战，喵！我们把它记作 $T_g$ ：

T_g = \sum_{\substack{1 \le d \le N \\ \gcd(d,N)=g}} \min_{k \in K_{min,g}}\{\text{rank}_d(kg)\}

首先，我们来搞清楚 $\text{rank}_d(kg)$ 是什么。它是第几次跳跃能到达 $kg$ 。这需要解一个同余方程： $t \cdot d \equiv kg \pmod N$ 。设 $d=gd', N=gN'$ ，其中 $\gcd(d', N')=1$ 。方程变为 $t \cdot gd' \equiv kg \pmod{gN'}$ ，也就是 $t \cdot d' \equiv k \pmod{N'}$ 。因为 $\gcd(d', N')=1$ ，所以 $d'$ 在模 $N'$ 意义下有逆元 $(d')^{-1}$ 。 $t \equiv k \cdot (d')^{-1} \pmod{N'}$ 。所以， $\text{rank}_d(kg)$ 就是 $t$ 的最小正整数解。我们把它记作 $(k \cdot (d/g)^{-1} \pmod{N/g})_1$ (结果在 $1$ 到 $N/g$ 之间)。

令 $u = (d/g)^{-1} \pmod{N/g}$ 。当 $d$ 遍历所有使 $\gcd(d,N)=g$ 的值时， $d/g$ 会遍历所有与 $N/g$ 互质的数。那么 $u$ 也会遍历所有与 $N/g$ 互质的数！所以 $T_g$ 可以华丽变身：

T_g = \sum_{\substack{1 \le u \le N/g \\ \gcd(u, N/g)=1}} \min_{k \in K_{min,g}}\{(k \cdot u \pmod{N/g})_1\}

这个式子我们记为 $\mathcal{T}(N/g, K_{min,g})$ 。

Step 4: 莫比乌斯反演登场！

这个 $\mathcal{T}(M, K)$ 还是很难直接求。但是，我们可以定义一个更容易计算的辅助函数：

\mathcal{S}(M, K) = \sum_{v=1}^M \min_{k \in K}\{(k \cdot v \pmod M)_1\}

这个函数对所有的 $v \in [1, M]$ 求和，而不是只对互质的求和。 $\mathcal{S}(M,K)$ 和 $\mathcal{T}(M,K)$ 之间有奇妙的关系！通过对 $\gcd(v,M)$ 进行分类，我们可以得到：

\mathcal{S}(M, K) = \sum_{d|M} d \cdot \mathcal{T}(M/d, K)

这是一个狄利克雷卷积的形式！ $S(n) = \sum_{d|n} id(d) T(n/d)$ ，其中 $id(d)=d$ 。这下就可以请出数论大法宝——莫比乌斯反演了！经过一番推导（或者说，对狄利克雷卷积求逆），我们可以得到从 $\mathcal{S}$ 反推 $\mathcal{T}$ 的公式：

\mathcal{T}(M, K) = M \sum_{d|M} \frac{\mathcal{S}(d, K)}{d} \mu\left(\frac{M}{d}\right)

其中 $\mu$ 是莫比乌斯函数。

太棒了！现在我们的路线图清晰了：

预处理 $\mu$ 和 $\phi$ 函数。
遍历 $N$ 的所有约数 $g$ 。
对每个 $g$ ，求出 $N' = N/g$ ，并找到对应的最小耐久度 $m_g$ 和最弱位置的指标集 $K_{min,g}$ 。
计算总和的第一部分： $\phi(N') \cdot (m_g-1) \cdot N'$ 。
计算第二部分 $T_g = \mathcal{T}(N', K_{min,g})$ 。为此，我们需要： a. 遍历 $N'$ 的所有约数 $M$ 。 b. 对每个 $M$ ，计算 $\mathcal{S}(M, K_{min,g}) = \sum_{v=1}^M \min_{k \in K_{min,g}}\{(k \cdot v \pmod M)_1\}$ 。这一步可以通过 $O(M \cdot |K_{min,g}|)$ 的暴力循环完成。 c. 利用上面的反演公式，代入所有求好的 $\mathcal{S}(M, K_{min,g})$ 值，算出 $\mathcal{T}(N', K_{min,g})$ 。
把两部分加起来，累加到最终答案。

虽然计算 $\mathcal{S}$ 的那一步看起来有点慢，但由于 $N$ 的约数个数和 $\sigma_1(N)$ （约数和函数）在 $10^5$ 范围内没有大到离谱，而且随机数据下 $|K_{min,g}|$ 通常很小，所以这个方法是可以通过的，喵~

代码实现

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MAXN = 100005;
const int MOD = 1004535809;

// --- 数据生成器 ---
unsigned seed, mod;
unsigned data_read() {
    seed ^= seed << 13;
    seed ^= seed >> 5;
    seed ^= seed << 7;
    return seed % mod + 1;
}

// --- 数论预处理 ---
int phi[MAXN];
int mu[MAXN];
bool is_prime[MAXN];
vector<int> primes;

void sieve(int n) {
    fill(is_prime, is_prime + n + 1, true);
    is_prime[0] = is_prime[1] = false;
    mu[1] = 1;
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            mu[i] = -1;
            phi[i] = i - 1;
        }
        for (int p : primes) {
            if ((ll)i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                mu[i * p] = 0;
                phi[i * p] = phi[i] * p;
                break;
            } else {
                mu[i * p] = -mu[i];
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
}

// --- 辅助函数 ---
vector<int> get_divisors(int n) {
    vector<int> divs;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            divs.push_back(i);
            if (i * i != n) {
                divs.push_back(n / i);
            }
        }
    }
    sort(divs.begin(), divs.end());
    return divs;
}

ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

ll mod_inverse(ll n) {
    return power(n, MOD - 2);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n >> seed >> mod;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        a[i] = data_read();
    }

    sieve(n);

    vector<int> n_divs = get_divisors(n);
    ll total_jumps = 0;

    for (int g : n_divs) {
        int n_prime = n / g;

        // Step 1: 找到 m_g 和 K_min,g
        int min_durability = 2e9;
        for (int k = 1; k <= n_prime; ++k) {
            min_durability = min(min_durability, a[k * g]);
        }
        vector<int> k_min;
        for (int k = 1; k <= n_prime; ++k) {
            if (a[k * g] == min_durability) {
                k_min.push_back(k);
            }
        }

        // Step 2: 计算总和的第一部分
        ll part1 = (ll)phi[n_prime] * (min_durability - 1) % MOD * n_prime % MOD;
        total_jumps = (total_jumps + part1) % MOD;

        // Step 3: 计算总和的第二部分 (T_g)
        vector<int> n_prime_divs = get_divisors(n_prime);
        map<int, ll> s_values;

        // 3a: 计算所有需要的 S(M, K)
        for (int M : n_prime_divs) {
            ll current_s = 0;
            for (int v = 1; v <= M; ++v) {
                int min_val = M;
                for (int k : k_min) {
                    min_val = min(min_val, (int)((ll)k * v % M == 0 ? M : (ll)k * v % M));
                }
                current_s = (current_s + min_val) % MOD;
            }
            s_values[M] = current_s;
        }
        
        // 3b: 使用莫比乌斯反演计算 T(N', K)
        ll t_g = 0;
        for (int d : n_prime_divs) {
            ll term = (ll)mu[n_prime / d] * s_values[d] % MOD;
            term = term * mod_inverse(d) % MOD;
            t_g = (t_g + term) % MOD;
        }
        t_g = (t_g * n_prime) % MOD;
        if (t_g < 0) t_g += MOD;

        total_jumps = (total_jumps + t_g) % MOD;
    }

    cout << total_jumps << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N \log \log N + \sum_{g|N} \sum_{M|N/g} M \cdot |K_{min,g}|)$
- 预处理筛法（sieve）的时间复杂度是 $O(N \log \log N)$ 。
- 主循环遍历 $N$ 的所有约数 $g$ 。对于每个 $g$ ，我们再遍历 $N/g$ 的所有约数 $M$ 来计算 $\mathcal{S}(M, K_{min,g})$ 。
- 计算 $\mathcal{S}(M, K_{min,g})$ 的复杂度是 $O(M \cdot |K_{min,g}|)$ 。
- 整个算法的主要开销在于计算所有的 $\mathcal{S}$ 函数值。总的计算量近似为 $\sum_{g|N} |K_{min,g}| \sum_{M|N/g} M = \sum_{g|N} |K_{min,g}| \sigma_1(N/g)$ ，其中 $\sigma_1$ 是约数和函数。
- 考虑到 $|K_{min,g}|$ 在随机数据下期望很小，复杂度可以近似看作 $\sum_{g|N} \sigma_1(N/g) = \sum_{d|N} \sigma_1(d)$ 。对于 $N \le 10^5$ ，这个值在可以接受的范围内。
空间复杂度: $O(N)$
- 主要空间开销来自于存储耐久度数组 $a$ 和预处理的数论函数数组 phi, mu 等，都需要 $O(N)$ 的空间。
- 存储约数的 vector 和计算 $\mathcal{S}$ 值的 map 所占空间远小于 $N$ 。

知识点总结

这道题是数论知识的盛宴，喵~ 解决它需要我们像小猫剥洋葱一样，一层层揭开问题的核心：

问题分解: 将复杂的大问题（求 $N$ 次跳跃总和）分解为更小的单元（求固定距离 $d$ 的跳跃次数）。
GCD 与环形结构: 认识到跳跃路径的周期性与 $\gcd(d, N)$ 密切相关，这是解题的第一个突破口。
分类讨论: 根据 $\gcd(d, N)$ 的值对问题进行分类，是处理和式 $\sum_{d=1}^N$ 的经典技巧。
欧拉函数: 用于计算与 $N$ 有特定公约数的数的个数。
狄利克雷卷积与莫比乌斯反演: 这是本题的灵魂！通过定义辅助函数 $\mathcal{S}$ 和目标函数 $\mathcal{T}$ ，我们发现它们之间构成了狄利克雷卷积关系，从而可以使用莫比乌斯反演从易于计算的 $\mathcal{S}$ 求出难以直接计算的 $\mathcal{T}$ 。这是解决数论中带有 gcd 条件求和问题的强大武器。

希望这篇题解能帮助你理解这道有趣的题目，喵~ 多练习数论题，你也能成为算法大师的！

Rolling Girl - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

Step 1: 分析单次逃脱过程 ​

Step 2: 汇总所有情况 ​

Step 3: 处理棘手的第二部分 ​

Step 4: 莫比乌斯反演登场！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​