G. I've Been Flipping Numbers for 300 Years and Calculated the Sum - 题解

比赛与标签

比赛: Codeforces Round 1006 (Div. 3) 标签: binary search, brute force, combinatorics, divide and conquer, math, number theory 难度: *2200

题目大意喵~

早上好，各位算法大师！今天我们来帮助一位英雄解决一个持续了三百年的难题，真是个大工程呢，喵~

题目是这样子的：我们需要计算一个超级大的和 x = ∑ (p=2 to k) rev(n, p)，最后结果对 10^9 + 7 取模。

这里的 rev(n, p) 是一个有趣的技能：

1. 先把数字 n 写成 p 进制的形式。
2. 然后把这个 p 进制数的各位数字反转过来。
3. 最后再把这个反转后的数从 p 进制转换回十进制。

比如说，rev(4, 2)：4 的二进制是 100，反转后是 001，转换回十进制就是 1 啦！

输入会给我们 n 和 k，其中 n 最大到 3 * 10^5，但 k 可能会非常非常大，达到 10^18！直接从 2 循环到 k 肯定是不行的说，会超时的喵。所以，我们需要更聪明的办法！

解题思路大解析！

看到 k 这么大，我们就知道这一定不是一道简单的暴力题，而是需要我们去发现规律，然后用数学方法来优化的说！我们可以根据 p 和 n 的大小关系，把这个求和分成几段来处理，就像把一个大蛋糕切成几块一样，一块一块吃掉它，喵~

我们来仔细分析一下 rev(n, p) 的性质吧！

第一块蛋糕：当 p > n 时

当底数 p 比要转换的数 n 还大的时候，n 的 p 进制表示就只有一位，就是 n 本身！比如 n=5, p=8，5 在 8 进制下就是 5。 反转一位数，它还是它自己。所以，当 p > n 时，rev(n, p) = n 恒成立！

那么，从 p = n + 1 到 k 这一段的和就是： ∑ (p=n+1 to k) n = n * (k - (n+1) + 1) = n * (k - n) 这一部分的和可以直接计算出来，耶！

第二块蛋糕：当 p <= n 时

这部分就比较复杂了，因为 p 在变化，n 的 p 进制表示的位数和各位数字也在变化。但是，我们可以再切一刀！喵~ 看我发现了什么，sqrt(n) 是一个神奇的分割点！

小份蛋糕：当 2 <= p <= sqrt(n) 时

当 p 比较小（不大于 sqrt(n)）的时候，n 在 p 进制下可能会有很多位，规律不明显。但是，这个范围并不大！因为 n <= 3 * 10^5，所以 sqrt(n) 大约是 550。 对于这么小的范围，我们完全可以直接暴力计算！写一个 get_rev(n, p) 函数，循环从 2 到 min(k, floor(sqrt(n)))，把每个 rev(n, p) 的值加起来。暴力出奇迹喵！

大份蛋糕：当 sqrt(n) < p <= n 时

当 p > sqrt(n) 时，p^2 > n。这意味着 n 写成 p 进制最多只有两位！ 我们可以把 n 表示成 n = d₁ * p + d₀，其中 d₁ = n / p (整除)，d₀ = n % p。 它的 p 进制表示就是 d₁d₀。 反转后就是 d₀d₁，转换回十进制就是 rev(n, p) = d₀ * p + d₁。 代入 d₁ 和 d₀，我们得到 rev(n, p) = (n % p) * p + (n / p)。

现在问题变成了求 ∑ (p=floor(sqrt(n))+1 to min(k, n)) ((n % p) * p + (n / p))。 直接求和还是太慢，但我们注意到 q = n / p 的值在 p 变化时，并不会一直变。它会在一段连续的 p 上保持不变！这就是整除分块的魔法！

对于一个固定的商 q，n / p = q 在哪个范围的 p 上成立呢？ p 的下界是 L，p 的上界是 R = n / q。 所以，我们可以遍历所有可能的商 q，对于每个 q，我们找到对应的 p 的区间 [L, R]，然后在这个区间上统一计算和。

对于区间 [L, R]，n/p 的值都是 q。我们需要计算： ∑ (p=L to R) ( (n - q*p) * p + q ) = ∑ (p=L to R) (n*p - q*p² + q)= n * ∑p - q * ∑p² + ∑q= n * ∑ (p=L to R) p - q * ∑ (p=L to R) p² + q * (R - L + 1)

∑p 和 ∑p² 都可以用自然数幂和公式来快速计算：

• ∑ (i=1 to m) i = m(m+1)/2
• ∑ (i=1 to m) i² = m(m+1)(2m+1)/6 我们可以预计算 2 和 6 在模 10^9 + 7 下的逆元，然后就可以 O(1) 计算任意区间的和啦！

总结一下我们的三步走策略：

1. 大 p 部分 (p > n): 直接用公式 n * (k - n) 计算。
2. 小 p 部分 (2 <= p <= sqrt(n)): 暴力循环计算 rev(n, p)。
3. 中 p 部分 (sqrt(n) < p <= n): 使用整除分块，结合数论求和公式进行计算。

把这三部分的结果加起来，就是最终的答案啦！是不是清晰多啦？喵~

代码实现喵~

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

using namespace std;

const long long MOD = 1000000007;

// 快速幂，用来求逆元，喵~
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 求模逆元，根据费马小定理，a^(p-2) 就是 a 在模 p 下的逆元
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

const long long INV2 = modInverse(2);
const long long INV6 = modInverse(6);

// 计算 1 + 2 + ... + m 的和，模 MOD
long long sum_1(long long m) {
    if (m < 0) return 0;
    long long m_mod = m % MOD;
    long long term1 = m_mod;
    long long term2 = (m_mod + 1);
    long long res = (term1 * term2) % MOD;
    res = (res * INV2) % MOD;
    return res;
}

// 计算 1^2 + 2^2 + ... + m^2 的和，模 MOD
long long sum_2(long long m) {
    if (m < 0) return 0;
    long long m_mod = m % MOD;
    long long term1 = m_mod;
    long long term2 = (m_mod + 1);
    long long term3 = (2 * m_mod + 1);
    long long res = (term1 * term2) % MOD;
    res = (res * term3) % MOD;
    res = (res * INV6) % MOD;
    return res;
}

// 直接计算 rev(n, p)，暴力出奇迹喵！
long long get_rev(long long n, long long p) {
    long long res = 0;
    long long temp_n = n;
    while (temp_n > 0) {
        res = res * p + (temp_n % p);
        temp_n /= p;
    }
    return res;
}

void solve() {
    long long n, k;
    cin >> n >> k;

    long long total_sum = 0;
    long long sq = sqrtl(n); // 使用 long double 的 sqrtl 保证精度

    // Part 1: p 从 2 到 min(sqrt(n), k)
    // 对于很小的 p，我们直接暴力计算 rev(n, p)
    long long limit1 = min((long long)sq, k);
    for (long long p = 2; p <= limit1; ++p) {
        total_sum = (total_sum + get_rev(n, p)) % MOD;
    }

    // Part 2: p 从 sqrt(n)+1 到 min(n, k)
    // 对于中等大小的 p，n 在 p 进制下最多两位，使用整除分块优化！
    if (k > sq) {
        long long limit2 = min(n, k);
        long long current_p = sq + 1;
        while (current_p <= limit2) {
            long long q = n / current_p;
            if (q == 0) break; // p > n 的情况，不应该在这里出现
            long long p_max_for_q = n / q;
            long long R = min(limit2, p_max_for_q);
            long long L = current_p;

            if (L > R) { // 避免空区间
                current_p = R + 1;
                continue;
            }

            // rev(n,p) = n*p - q*p^2 + q
            // 我们要求和：n*sum(p) - q*sum(p^2) + q*count
            long long s1_R = sum_1(R);
            long long s1_L_1 = sum_1(L - 1);
            long long s2_R = sum_2(R);
            long long s2_L_1 = sum_2(L - 1);

            long long sum_p = (s1_R - s1_L_1 + MOD) % MOD;
            long long sum_p2 = (s2_R - s2_L_1 + MOD) % MOD;
            long long count = R - L + 1;

            long long term1 = (n % MOD * sum_p) % MOD;
            long long term2 = (q % MOD * sum_p2) % MOD;
            long long term3 = (q % MOD * (count % MOD)) % MOD;

            long long range_sum = (term1 - term2 + term3 + MOD) % MOD;
            total_sum = (total_sum + range_sum) % MOD;

            current_p = R + 1; // 跳到下一个分块的开始
        }
    }

    // Part 3: p 从 n+1 到 k
    // 对于很大的 p，rev(n, p) = n
    if (k > n) {
        long long count = k - n;
        long long term = (count % MOD * (n % MOD)) % MOD;
        total_sum = (total_sum + term) % MOD;
    }

    cout << total_sum << endl;
}

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

复杂度分析的说

• 时间复杂度: O(sqrt(n) * log(n)) 的说
  • 第一部分（暴力）的循环次数是 O(sqrt(n))，每次计算 rev 需要 O(log_p(n)) 的时间，总共是 O(sqrt(n) * log(n))。
  • 第二部分（整除分块）的块数是 O(sqrt(n))，每个块的计算是 O(1)，总共是 O(sqrt(n))。
  • 第三部分（大p）是 O(1) 的。
  • 所以总的时间复杂度由最慢的部分决定，就是 O(sqrt(n) * log(n)) 啦！对于 n=3*10^5 来说，完全可以接受。
• 空间复杂度: O(1) 的说
  • 我们只用到了几个变量来存储中间结果，没有使用随输入规模增大的数据结构，所以空间是常数级别的。

知识点与总结

这真是一道融合了多种技巧的有趣题目呢，喵~ 解开它就像完成了一次精彩的冒险！

• 分段处理思想: 核心思想就是根据 p 和 n 的关系，将问题分解成几个不同性质的子问题。这是解决复杂问题时非常有效的一种策略！
• 整除分块: 对于形如 sum(f(i, n/i)) 的求和，整除分块是超级给力的优化技巧。它能把 O(N) 的复杂度降到 O(sqrt(N))，一定要掌握哦！
• 数论求和公式: 熟练使用自然数幂和公式（sum(i), sum(i^2)等）可以帮助我们快速计算区间和。
• 模运算与逆元: 只要题目涉及取模，就要时刻注意！乘法和加减法都要取模，除法要转换为乘以它的模逆元。

只要把大问题分解成小块，再难的题目也能解决的喵！希望这篇题解能帮到你，继续加油呀，未来的大算法家！