[COCI2012-2013#1] SNAGA 题解

前言

题目链接：洛谷。

题意简述

定义 \(f(x)\) 表示不能整除 \(x\) 的最小正整数。

给出数字 \(n\)，每次 \(n \gets f(n)\)，当 \(n = 2\) 时停止。定义 \(g(n)\) 为这一过程中的数字个数，例如 \(g(6) = 4\)。给定 \(l, r\)，求 \(\sum \limits _ {i = l} ^ r g(i)\)。

\(3 \leq l \lt r \leq 10^{18}\)。

题目分析

首先发现 \(f(x)\) 非常小，在 \(x \leq 10^{18}\) 时，有 \(n = \max f(x) = 41\)。所以，我们枚举 \(i = 1, \ldots, n\)，每次统计在 \([l, r]\) 中，\(f(x) = i\) 的个数有多少个，这些数的 \(g\) 函数值都是 \(g(i) + 1\)，所以将个数乘上 \(g(i) + 1\) 就可以累加到答案中去了。得到 \(1 \sim n\) 的 \(g\) 的函数值是简单的。容易证明，这样的统计是不重不漏的。

我们怎么求出 \(f(x) = i\) 的个数呢？发现，“不能整除 \(x\) 的最小正整数”等价于“能够整除小于它的所有正整数，但不能整除它”，换句话说，\(f(x) = i\) 的 \(x\) 满足 \(\forall t \in [1, i), t \mid x\) 以及 \(i \not \mid x\)。不妨从前者中扣出后者，即两个条件同时满足的很难计算，那么我们先计算满足 \(A\) 的方案数，减去满足 \(A\) 但不满足 \(B\) 的方案数。

前者又等价于 \(\operatorname{lcm}(1, \ldots, i - 1) \mid x\)，不妨记 \(p_i = \operatorname{lcm}(1, \ldots, i)\)，前者等价于 \(p_{i - 1} \mid x\)。所以 \([l, r]\) 中，能够整除 \(p_{i - 1}\) 的个数，等价于是 \(p_{i - 1}\) 的倍数的个数，也就是 \(\Big \lfloor \cfrac{r}{p_{i - 1}} \Big \rfloor - \Big \lfloor \cfrac{l - 1}{p_{i - 1}} \Big \rfloor\)。

再来看看满足前者但不满足后者的个数。此时 \(p_{i - 1} \mid x\) 并且 \(i \mid x\)。发现其实就是 \(p_i \mid x\)，用同样的方法计数即可。

形式化地讲，答案 \(ans = \sum \limits _ {i = 2} ^ {41} {\Large {\Bigg (}} \Bigg ( \Big \lfloor \cfrac{r}{p_{i - 1}} \Big \rfloor - \Big \lfloor \cfrac{l - 1}{p_{i - 1}} \Big \rfloor \Bigg ) - \Bigg ( \Big \lfloor \cfrac{r}{p_{i}} \Big \rfloor - \Big \lfloor \cfrac{l - 1}{p_{i}} \Big \rfloor \Bigg ) {\Large {\Bigg )}} \times \Big ( g(i) + 1 \Big)\)。

\(f, g\) 什么的打个表预处理一下，时间复杂度 \(\Theta(\max f(x))\)。

代码

#include <cstdio>
#include <iostream>
#include <array>
using namespace std;

constexpr int f(int x) {
    for (int i = 2;; ++i)
        if (x % i)
            return i;
}

constexpr const int N = 41;

template <typename T>
using arr = array<T, N + 1>;
using lint = long long;

constexpr arr<int> len = []() {
    arr<int> res = {};
    res[2] = 1;
    for (int i = 3; i <= N; ++i) res[i] = res[f(i)] + 1;
    return res;
}();

template <typename T>
constexpr T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}
template <typename T>
constexpr T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

constexpr arr<lint> val = []() {
    arr<lint> res = {};
    res[1] = 1;
    for (int i = 2; i <= N; ++i) res[i] = lcm(res[i - 1], 1ll * i);
    return res;
}();

lint l, r, res;

signed main() {
    scanf("%lld%lld", &l, &r);
    for (int i = 2; i <= N; ++i)
        res += ((r / val[i - 1] - (l - 1) / val[i - 1]) - (r / val[i] - (l - 1) / val[i])) * (len[i] + 1);
    printf("%lld", res);
    return 0;
}

反思 & 总结

遇到数据范围巨大的时候，考虑：倍增、矩阵快速幂、数位 DP、根号分治、数学性质。

本题属于最后一类，关键点在于发现 \(\operatorname{lcm}\) 很小，并转变计数视角，使用小小容斥计数。