Function - 题解

标签与难度

标签: 数论, 积性函数, Min_25筛, 费马平方和定理, 筛法难度: 2500

题目大意喵~

主人你好呀，欢迎来到我的算法小课堂！今天我们要解决一个关于神奇函数的问题，喵~

题目定义了几个函数：

csl(p, x): 基础形式是 $csl(p, x) = 3\log_{p}x + 1$ $cs l (p, x) = 3 lo g_{p} x + 1$ 。但它有几个特殊的规矩哦：
- 如果 $3\log_{p}x + 1$ 不是整数，那么 $csl(p, x) = 0$ 。
- 如果结果是整数，但底数 $p$ 是 $2$ 或者 $p$ 不能被写成两个正整数的平方和（ $p \ne a^2+b^2$ ），那么 $csl(p, x) = 1$ 。
tl(p, d): 这个函数是 $csl$ 函数的加强版，它会取一个数 $d$ 的所有约数 $k$ ，然后计算所有 $csl(p, k)$ 的最大值，也就是 $tl(p, d) = \max_{k|d}(csl(p, k))$ 。
最终目标: 给定一个正整数 $n$ ，我们需要计算下面这个式子的值： $\sum_{d=1}^{n} \prod_{p} tl(p, d)$ 这里的 $\prod_p$ 表示对所有的素数 $p$ 求乘积。

看起来有点复杂，对吧？别担心，跟着我一步一步来，我们会把这个大怪兽拆解成一堆小猫咪的，喵~

解题思路分析

这道题就像一个神秘的毛线球，我们要做的就是找到线头，然后把它一点点解开，呐。

第一步：解开 `csl(p, x)` 的秘密

首先我们来分析 csl(p, x) 函数。

$3\log_{p}x + 1$ 必须是整数。这要求 $\log_{p}x$ 必须是整数（因为如果 $\log_p x$ 是分数，比如 $a/b$ 且 $b \ne 1,3$ ，那 $3\log_p x$ 也很难是整数）。当 $\log_p x$ 是整数 $k$ 时， $x$ 必须是 $p$ 的整数次幂，也就是 $x = p^k$ （其中 $k \ge 0$ ）。如果 $x$ 不是 $p$ 的幂，那么 $csl(p, x) = 0$ 。
当 $x = p^k$ 时， $csl(p, x) = 3k+1$ 。
接下来看第二个条件：如果 $p=2$ $p = 2$ 或者 $p$ $p$ 不能表示为两个正整数的平方和，那么 $csl(p, x)$ $cs l (p, x)$ 的值强制变成 $1$ $1$ 。
- 这里有一个非常漂亮的数论定理，叫做 费马平方和定理！它告诉我们，一个奇素数 $p$ 可以表示为两个平方数之和，当且仅当 $p \equiv 1 \pmod 4$ 。
- 素数 $2$ 本身可以写成 $1^2+1^2$ 。但是题目条件是 “ $p=2$ 或者 $p$ 不能...”，所以 $p=2$ 是一个独立的分支。
- 不能表示为两平方和的奇素数，根据费马定理，就是那些满足 $p \equiv 3 \pmod 4$ 的素数。
- 所以，这个条件可以翻译成：如果 $p=2$ 或者 $p \equiv 3 \pmod 4$ ，那么 $csl(p, p^k)=1$ 。
- 反之，如果 $p \equiv 1 \pmod 4$ ，那么 $csl(p, p^k) = 3k+1$ 。

总结一下 csl(p, p^k) 的值：

csl(p, p^k) = \begin{cases} 3k+1 & \text{如果 } p \equiv 1 \pmod 4 \\ 1 & \text{如果 } p=2 \text{ 或 } p \equiv 3 \pmod 4 \end{cases}

第二步：分析 `tl(p, d)` 和最终的乘积

现在来看 $tl(p, d) = \max_{k|d}(csl(p, k))$ 。因为 $csl(p, k)$ 只在 $k$ 是 $p$ 的幂时才不为零，所以我们只需要在 $d$ 的约数中，寻找那些是 $p$ 的幂的数。假设 $d$ 的质因数分解中， $p$ 的最高次幂是 $a$ ，即 $p^a || d$ 。那么 $d$ 的约数中 $p$ 的幂有 $p^0, p^1, \dots, p^a$ 。 $tl(p, d) = \max \{csl(p, p^0), csl(p, p^1), \dots, csl(p, p^a)\}$ 。

如果 $p \equiv 1 \pmod 4$ ，那么 $csl(p, p^k) = 3k+1$ 。这是一个关于 $k$ 的递增函数，所以最大值在 $k=a$ 时取得，即 $tl(p, d) = 3a+1$ 。
如果 $p=2$ 或 $p \equiv 3 \pmod 4$ ，那么 $csl(p, p^k) = 1$ 对所有 $k \ge 0$ 成立。所以最大值就是 $1$ 。

现在我们来看最终要求的那个大式子里的乘积项 $F(d) = \prod_{p} tl(p, d)$ 。

如果一个素数 $p$ 不是 $d$ 的因子，那么 $p$ 在 $d$ 中的最高次幂是 $0$ ( $a=0$ )。此时 $tl(p, d) = csl(p, p^0) = 3(0)+1 = 1$ 。
这意味着，这个无穷乘积中，只有 $p$ 是 $d$ 的质因子时， $tl(p,d)$ 才可能不是 $1$ 。所以乘积实际上是有限的！

设 $d = p_1^{a_1} p_2^{a_2} \dots p_m^{a_m}$ 。

F(d) = \prod_{i=1}^{m} tl(p_i, d) = \prod_{i=1}^{m, \ p_i \equiv 1 \pmod 4} (3a_i+1)

哇！我们发现 $F(d)$ 是一个 积性函数 呢！对于两个互质的数 $m$ 和 $n$ ， $F(mn)=F(m)F(n)$ 。证明很简单，因为 $m, n$ 互质，它们的质因子集合不相交，所以 $F(mn)$ 的乘积式可以直接拆成 $F(m)$ 和 $F(n)$ 的乘积。

第三步：选择终极武器——Min_25筛！

问题转化成了：求一个积性函数 $F(d)$ 的前缀和 $\sum_{d=1}^{n} F(d)$ 。对于 $n$ 很大（比如 $10^{10}$ ）的情况，这正是 Min_25筛 的主场！喵~ Min_25筛是一种能在亚线性时间复杂度内求积性函数前缀和的强大算法。

Min_25筛分为两个部分：

第一部分：计算 $F(p)$ 在所有素数 $p$ 上的和。我们的 $F(p)$ （也就是 $F(p^1)$ ）的值是：
$F(p) = \begin{cases} 4 & \text{如果 } p \equiv 1 \pmod 4 \\ 1 & \text{如果 } p=2 \text{ 或 } p \equiv 3 \pmod 4 \end{cases}$
$F(p)$ 的值依赖于 $p \pmod 4$ 。所以我们需要分别计算出在所有 $\lfloor n/i \rfloor$ 的取值点上，有多少个素数满足 $p \equiv 1 \pmod 4$ 和 $p \equiv 3 \pmod 4$ 。我们可以用一个类似动态规划的思路来筛。设 $g_1[k]$ 和 $g_3[k]$ 分别表示在 $[1, w_k]$ 范围内，最小质因子大于 primes[j-1] 的、模4余1和余3的数的个数。当我们用第 $j$ 个素数 primes[j] 去筛时：
- 如果 primes[j] $\equiv 1 \pmod 4$ ，那么它乘上一个模4余1的数，结果还是模4余1；乘上一个模4余3的数，结果还是模4余3。
- 如果 primes[j] $\equiv 3 \pmod 4$ ，那么它乘上一个模4余1的数，结果是模4余3；乘上一个模4余3的数，结果是模4余9，也就是模4余1。这里会发生一个有趣的“交换”！通过这个DP过程，我们就能求出所有需要的素数计数。
第二部分：递归计算最终的答案。我们定义一个递归函数 $S(x, j)$ ，表示在 $[1, x]$ 范围内，所有最小质因子大于等于第 $j$ 个素数 primes[j] 的数 $d$ 的 $F(d)$ 之和。 $S(x, j)$ 的值由两部分构成：
- 素数的贡献：所有大于等于 primes[j] 且小于等于 $x$ 的素数 $p$ 的 $F(p)$ 之和。这部分可以用第一步预处理出的信息快速计算。
- 合数的贡献：所有最小质因子为 $p_i$ ( $i \ge j$ ) 的合数。我们可以枚举这个最小质因子 $p_i$ 和它的次幂 $e$ 。一个这样的合数可以写成 $p_i^e \cdot m$ ，其中 $m$ 的最小质因子大于 $p_i$ 。这部分的贡献可以通过递归调用 $S(x/p_i^e, i+1)$ 来计算。

最终的答案就是 $S(n, 1) + F(1)$ 。因为我们的 $S$ 函数只计算了大于1的数的贡献，所以别忘了加上 $F(1)=1$ 哦！

代码实现

这是我为你精心准备的代码，注释超详细的喵~

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>

using namespace std;

typedef long long ll;

const int MAX_SQRT_N = 100005; // n <= 10^10, sqrt(n) <= 10^5

ll n;
int sqrt_n;

// w[k] 存储所有 n/i 的值
// id1 和 id2 用于快速定位 w[k] 的索引
ll w[MAX_SQRT_N * 2];
int id1[MAX_SQRT_N], id2[MAX_SQRT_N];
int m; // w 数组的大小

// 预处理 sqrt(n) 内的素数
int primes[MAX_SQRT_N];
int p_count;
bool is_not_prime[MAX_SQRT_N];
// p_sum1[i] = sum_{j=1..i, primes[j]%4==1} 1
// p_sum3[i] = sum_{j=1..i, primes[j]%4==3} 1
ll p_sum1[MAX_SQRT_N];
ll p_sum3[MAX_SQRT_N];

// Min_25筛第一部分的DP数组
// g1[k]: 在 [1, w[k]] 范围内, 最小质因子 > primes[j] 的数中, 模4余1的个数
// g3[k]: 在 [1, w[k]] 范围内, 最小质因子 > primes[j] 的数中, 模4余3的个数
ll g1[MAX_SQRT_N * 2];
ll g3[MAX_SQRT_N * 2];

// 线性筛预处理 sqrt(n) 内的素数及其性质
void linear_sieve(int limit) {
    p_count = 0;
    fill(is_not_prime, is_not_prime + limit + 1, false);
    is_not_prime[0] = is_not_prime[1] = true;
    for (int i = 2; i <= limit; ++i) {
        if (!is_not_prime[i]) {
            primes[++p_count] = i;
            p_sum1[p_count] = p_sum1[p_count - 1] + (i % 4 == 1);
            p_sum3[p_count] = p_sum3[p_count - 1] + (i % 4 == 3);
        }
        for (int j = 1; j <= p_count && i * primes[j] <= limit; ++j) {
            is_not_prime[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

// 计算 F(p^k) 的值
ll F_pk(ll p, int k) {
    if (p % 4 == 1) {
        return 3 * (ll)k + 1;
    }
    return 1;
}

// Min_25筛第二部分：递归计算S(x, j)
ll calculate_S(ll x, int j) {
    // 递归边界：如果没有素数可以筛了，或者 x 太小了
    if (x < primes[j] || x <= 1) {
        return 0;
    }

    // 获取 x 对应的索引 k
    int k = (x <= sqrt_n) ? id1[x] : id2[n / x];
    
    // 计算素数的贡献
    // H(x) - H(primes[j-1])
    // H(x) = 4 * (g1[k] - 1 for p=2) + (g3[k]) + 1 for p=2 = 4*g1[k] + g3[k] + (x>=2?1:0)
    // 这里 g1, g3 是对奇素数统计的，所以 2 要单独考虑
    // F(p)=4 for p%4=1, F(p)=1 for p%4=3.
    // Sum F(p) = Sum 4*I(p%4==1) + 1*I(p%4==3) = 3*I(p%4==1) + (I(p%4==1)+I(p%4==3))
    // Sum over p > primes[j-1]
    ll prime_contribution = 3 * (g1[k] - p_sum1[j - 1]); // 3 * (count of primes = 1 mod 4)
    prime_contribution += (g1[k] - p_sum1[j - 1]); // + (count of primes = 1 mod 4)
    prime_contribution += (g3[k] - p_sum3[j - 1]); // + (count of primes = 3 mod 4)

    ll result = prime_contribution;

    // 递归计算合数的贡献
    for (int i = j; i <= p_count && (ll)primes[i] * primes[i] <= x; ++i) {
        ll p = primes[i];
        ll pk = p; // p^1
        for (int e = 1; pk <= x / p; ++e) {
            pk *= p; // pk = p^(e+1)
            // 加上 F(p^e) * S(x/p^e, i+1) 和 F(p^{e+1})
            result += F_pk(p, e) * calculate_S(x / (pk / p), i + 1) + F_pk(p, e + 1);
        }
    }
    return result;
}

void solve() {
    cin >> n;
    if (n == 0) {
        cout << 0 << endl;
        return;
    }

    sqrt_n = sqrt(n);
    m = 0;

    // 初始化 w 数组，存储所有 n/i 的值
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        w[++m] = n / l;
    }

    // 初始化 id1, id2 映射
    // 初始化 g1, g3 数组 (DP初始状态)
    for (int i = 1; i <= m; ++i) {
        ll val = w[i];
        if (val <= sqrt_n) id1[val] = i;
        else id2[n / val] = i;
        
        // 初始时，g1/g3 包含所有 > 1 的奇数
        g1[i] = (val >= 1) ? (val - 1) / 4 : 0;
        g3[i] = (val >= 3) ? (val - 3) / 4 + 1 : 0;
    }

    // Min_25筛第一部分：DP过程
    // p_count 是 sqrt(n) 范围内的素数个数, primes[1]=2
    for (int j = 2; j <= p_count; ++j) { // 从 p=3 开始筛
        ll p = primes[j];
        if (p * p > n) break;
        for (int i = 1; i <= m && p * p <= w[i]; ++i) {
            ll next_val = w[i] / p;
            int k = (next_val <= sqrt_n) ? id1[next_val] : id2[n / next_val];
            if (p % 4 == 1) {
                g1[i] -= (g1[k] - p_sum1[j - 1]);
                g3[i] -= (g3[k] - p_sum3[j - 1]);
            } else { // p % 4 == 3
                g1[i] -= (g3[k] - p_sum3[j - 1]);
                g3[i] -= (g1[k] - p_sum1[j - 1]);
            }
        }
    }
    
    // 答案是 S(n, 1) + F(1)
    // S(n, 1) 计算所有 > 1 的数的贡献
    // F(1) = 1
    // S(n, 1) 里面需要算上 F(2)=1 的贡献
    cout << calculate_S(n, 1) + 1 + (n >= 2 ? 1 : 0) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    linear_sieve(MAX_SQRT_N - 1);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}

代码逻辑微调说明: 在 calculate_S 中，素数部分的贡献是 H(x) - H(primes[j-1])。H(x) 是所有小于等于 x 的素数 p 的 F(p) 之和。 $F(p)=1$ 对 $p=2$ 和 $p \equiv 3 \pmod 4$ 成立。 $F(p)=4$ 对 $p \equiv 1 \pmod 4$ 成立。所以 $\sum F(p) = \sum_{p\text{ prime}} 1 + \sum_{p \equiv 1 \pmod 4} 3$ 。我的代码中，g1 和 g3 是对奇素数进行统计的，所以 calculate_S 计算的是奇素数的贡献。最后在 main 函数的结果中，我手动加上了 F(2)=1 的贡献（当 n >= 2 时）。

复杂度分析

时间复杂度: Min_25筛的经典时间复杂度是 $O(\frac{n^{3/4}}{\log n})$ 。但在实践中，由于整数除法的性质，它的表现通常优于这个上界，更接近 $O(n^{1-\epsilon})$ 。对于 $n=10^{10}$ 的数据规模，这个算法是完全可以接受的，喵~
空间复杂度: 我们需要存储直到 $\sqrt{n}$ 的素数和对应的一些数组，以及为所有 $\lfloor n/i \rfloor$ 的值（大约 $2\sqrt{n}$ 个）存储DP数组。所以空间复杂度是 $O(\sqrt{n})$ 。

知识点总结

这道题是一场美妙的数论探险，我们用到了：

积性函数: 能够将复杂问题分解的关键性质。识别出题目中的函数是积性的是破局的第一步。
费马平方和定理: 一个优雅的数论定理，帮助我们简化了题目中的判断条件。
Min_25筛: 解决积性函数前缀和问题的终极武器！它结合了筛法、数论和动态规划的思想，非常强大。
分块与数论函数求和: 对 $\lfloor n/i \rfloor$ 进行分块处理和索引是Min_25筛以及很多数论题目中的常见技巧。

希望我的讲解能帮助你理解这道题！解题就像逗猫棒，只要你耐心寻找角度，总能找到最好玩的那个点，加油喵~！

Function - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：解开 csl(p, x) 的秘密 ​

第二步：分析 tl(p, d) 和最终的乘积 ​

第三步：选择终极武器——Min_25筛！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​