CF2072G 题解

1. 题目分析

题意简述

给定 $n,k$，对所有 $2\le p\le k$ 求 $\operatorname{rev}(n,p)$ 的和。其中 $\operatorname{rev}(n,p)$ 表示把 $n$ 的 $p$ 进制表示反转后，再转回十进制。

难点剖析

$k$ 最大可达 $10^{18}$，不能枚举所有进制。另一方面 $n\le 3\cdot 10^5$，这提示我们应该围绕 $n$ 而不是 $k$ 分段。

有一个很关键的特判：当 $p>n$ 时，$n$ 在 $p$ 进制下只有一位，所以反转后仍然是 $n$。因此所有 $p=n+1,n+2,\ldots,k$ 的贡献可以一次性计算。

2. 从暴力到正解

策略一：直接枚举进制

最直接的做法是枚举 $p=2$ 到 $k$，每次模拟进制转换和反转。一次反转需要 $O(\log_p n)$，总复杂度大约是 $O(k\log n)$。

这个做法只适合 $k$ 很小的情况。由于 $k$ 可以达到 $10^{18}$，显然不能通过。

策略二：按表示长度分块

如果 $p>\sqrt n$ 且 $p\le n$，那么 $n$ 在 $p$ 进制下最多只有两位。设

$$n=qp+r,\quad q=\left\lfloor\frac np\right\rfloor,\quad r=n\bmod p$$

则 $n$ 的 $p$ 进制表示是 $\overline{qr}_p$，反转后是 $\overline{rq}_p$，即

$$\operatorname{rev}(n,p)=rp+q=(n-qp)p+q=np-qp^2+q$$

因此只要能在一段区间内让 $q=\lfloor n/p\rfloor$ 保持不变，就可以用平方和公式批量计算贡献。

3. 正解思路

如何想到正解

瓶颈在于进制 $p$ 太多，但当 $p$ 变大时，$n$ 的 $p$ 进制位数会迅速减少。于是按 $p$ 和 $\sqrt n$ 的关系分成三类：

1. $2\le p\le \lfloor\sqrt n\rfloor$：进制较小，数量只有 $O(\sqrt n)$，直接模拟。
2. $\lfloor\sqrt n\rfloor<p\le n$：表示最多两位，用整除分块计算。
3. $p>n$：表示只有一位，每个贡献都是 $n$。

对于第二类，固定 $q=\lfloor n/p\rfloor$ 后，所有满足该 $q$ 的 $p$ 构成一个连续区间 $[L,R]$，其中 $R=\lfloor n/q\rfloor$。在这个区间内贡献和为

$$\sum_{p=L}^{R}(np-qp^2+q) =n\sum_{p=L}^{R}p-q\sum_{p=L}^{R}p^2+q(R-L+1)$$

使用等差数列求和与平方和公式即可。

算法步骤

1. 令 $s=\lfloor\sqrt n\rfloor$。
2. 若 $k>n$，先加入 $(k-n)n$，表示所有 $p>n$ 的贡献。
3. 对 $p=2$ 到 $\min(k,s)$ 直接模拟 $\operatorname{rev}(n,p)$。
4. 对 $p=s+1$ 到 $\min(k,n)$ 做整除分块：
   • 当前左端点为 $L$；
   • 令 $q=\lfloor n/L\rfloor$；
   • 当前块右端点为 $R=\min(\min(k,n),\lfloor n/q\rfloor)$；
   • 用公式加入这一整段贡献；
   • 令 $L=R+1$ 继续。

正确性说明

对于 $p>n$，$n$ 在 $p$ 进制下是一位数，反转不改变数值，所以贡献恒为 $n$。

对于 $p\le \sqrt n$，算法逐个模拟定义，因此贡献正确。

对于 $\sqrt n<p\le n$，有 $\lfloor n/p\rfloor<p$，所以 $n$ 的 $p$ 进制表示至多两位。设 $n=qp+r$，反转后数值为 $rp+q$，代入 $r=n-qp$ 得到 $np-qp^2+q$。整除分块保证同一块内 $q$ 不变，因此可以用求和公式一次性算出这一块的总贡献，且所有块不重不漏覆盖整个区间。

综上，三类区间覆盖了所有 $2\le p\le k$，每一类贡献都被正确计算。

复杂度分析

直接模拟部分有 $O(\sqrt n)$ 个进制。整除分块部分也只有 $O(\sqrt n)$ 个块。每个测试用例的时间复杂度为 $O(\sqrt n\log n)$，其中 $\log n$ 来自小进制下的反转模拟；空间复杂度为 $O(1)$。

4. 参考代码（C++14）

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

using int64 = long long;

const int64 MOD = 1000000007LL;
const int64 INV2 = 500000004LL;
const int64 INV6 = 166666668LL;

int64 add_mod(int64 a, int64 b) {
    a %= MOD;
    b %= MOD;
    int64 res = a + b;
    if (res >= MOD) res -= MOD;
    return res;
}

int64 sub_mod(int64 a, int64 b) {
    a %= MOD;
    b %= MOD;
    int64 res = a - b;
    if (res < 0) res += MOD;
    return res;
}

int64 mul_mod(int64 a, int64 b) {
    return (a % MOD) * (b % MOD) % MOD;
}

int64 sum_p(int64 r) {
    if (r <= 0) return 0;
    return mul_mod(mul_mod(r, r + 1), INV2);
}

int64 sum_p(int64 l, int64 r) {
    if (l > r) return 0;
    return sub_mod(sum_p(r), sum_p(l - 1));
}

int64 sum_p2(int64 r) {
    if (r <= 0) return 0;
    return mul_mod(mul_mod(mul_mod(r, r + 1), 2 * r + 1), INV6);
}

int64 sum_p2(int64 l, int64 r) {
    if (l > r) return 0;
    return sub_mod(sum_p2(r), sum_p2(l - 1));
}

// 按定义模拟 rev(n,p)，用于小进制部分。
int64 rev_base(int64 n, int64 p) {
    int64 res = 0;
    while (n > 0) {
        res = add_mod(mul_mod(res, p), n % p);
        n /= p;
    }
    return res;
}

int64 direct_sum(int64 n, int64 r) {
    int64 res = 0;
    for (int64 p = 2; p <= r; ++p) {
        res = add_mod(res, rev_base(n, p));
    }
    return res;
}

// 处理 sqrt(n)<p<=n，此时 n 的 p 进制表示最多两位。
int64 two_digit_sum(int64 n, int64 l, int64 r) {
    if (l > r) return 0;

    int64 res = 0;
    int64 L = l;
    while (L <= r) {
        int64 q = n / L;
        int64 R = min(r, n / q);

        // rev(n,p)=n*p-q*p^2+q，q 在 [L,R] 内不变。
        int64 part = mul_mod(n, sum_p(L, R));
        part = sub_mod(part, mul_mod(q, sum_p2(L, R)));
        part = add_mod(part, mul_mod(q, R - L + 1));
        res = add_mod(res, part);

        L = R + 1;
    }
    return res;
}

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

    int t;
    cin >> t;
    while (t--) {
        int64 n, k;
        cin >> n >> k;

        // 计算 floor(sqrt(n))，再微调避免浮点误差。
        int64 sq = sqrtl((long double)n);
        while ((sq + 1) * (sq + 1) <= n) ++sq;
        while (sq * sq > n) --sq;

        int64 ans = 0;

        // p>n 时只有一位，贡献恒为 n。
        if (k > n) {
            ans = add_mod(ans, mul_mod(k - n, n));
        }

        // 小进制直接模拟。
        ans = add_mod(ans, direct_sum(n, min(k, sq)));

        // 大于 sqrt(n) 且不超过 n 的部分使用整除分块。
        ans = add_mod(ans, two_digit_sum(n, sq + 1, min(k, n)));

        cout << ans << '\n';
    }

    return 0;
}