KM and M - 题解

标签与难度

标签: 数学, 数论, 类欧几里得算法, 位运算, 模运算, __int128 难度: 2300

题目大意喵~

主人你好呀！这道题是让我们计算一个看起来有点复杂的求和式，喵~

具体来说，给定两个正整数 $N$ 和 $M$ ，我们需要计算下面这个式子的值：

\sum_{k = 1}^{N} ((k \cdot M) \ \& \ M)

其中 & 代表按位与（Bitwise AND）运算。最后的结果需要对 $10^9 + 7$ 取模。

$N$ 和 $M$ 的值可能会非常大，所以直接从 1 到 $N$ 循环计算肯定会超时哦，我们需要找到更聪明的办法，呐！

解题思路分析

看到这个题目，一个直接的想法就是写一个循环，从 $k=1$ 到 $N$ ，一步步累加 (k * M) & M 的值。但是 $N$ 可以很大很大（比如到 $10^{18}$ ），这样的 $O(N)$ 暴力解法肯定是不行的啦，会等到猫咪的胡子都白了也算不完的，喵~

既然有位运算 &，这通常是一个强烈的信号，提示我们可以把问题拆解到二进制的每一个位上进行考虑！

我们要求的和是 $S = \sum_{k=1}^{N} ((kM) \& M)$ 。一个数 $X$ 可以表示为它所有二进制位的权值之和，也就是 $X = \sum_{i=0}^{\infty} \text{bit}_i(X) \cdot 2^i$ ，其中 $\text{bit}_i(X)$ 是 $X$ 在二进制表示下第 $i$ 位的值（0 或 1）。

那么我们的总和 $S$ 也可以这样拆分：

S = \sum_{k=1}^{N} \left( \sum_{i=0}^{\text{max_bits}} \text{bit}_i((kM) \& M) \cdot 2^i \right)

交换一下求和的顺序，对我们分析问题更有利哦：

S = \sum_{i=0}^{\text{max_bits}} 2^i \cdot \left( \sum_{k=1}^{N} \text{bit}_i((kM) \& M) \right)

现在，我们来分析一下里面的 $\text{bit}_i((kM) \& M)$ 。根据按位与的性质， $(kM) \& M$ 的第 $i$ 位为 1，当且仅当 $kM$ 的第 $i$ 位为 1 并且 $M$ 的第 $i$ 位为 1。

如果 $M$ 的第 $i$ 位是 0，那么无论 $kM$ 的第 $i$ 位是什么， $(kM) \& M$ 的第 $i$ 位永远是 0。这一位对总和的贡献就是 0。
如果 $M$ 的第 $i$ 位是 1，那么 $(kM) \& M$ 的第 $i$ 位就完全取决于 $kM$ 的第 $i$ 位。此时， $\text{bit}_i((kM) \& M) = \text{bit}_i(kM)$ 。

所以，我们只需要对那些 $M$ 的第 $i$ 位为 1 的位进行计算！问题就转化为了，对于每个使得 $\text{bit}_i(M)=1$ 的 $i$ ，计算出 $\sum_{k=1}^{N} \text{bit}_i(kM)$ 的值，然后乘以 $2^i$ 累加到最终答案里。

那么，如何高效地计算 $\sum_{k=1}^{N} \text{bit}_i(kM)$ 呢？这里有一个非常关键的小技巧，喵~ 一个数 $X$ 的第 $i$ 位的值，可以用下取整函数来表示：

\text{bit}_i(X) = \left\lfloor \frac{X}{2^i} \right\rfloor - 2 \cdot \left\lfloor \frac{X}{2^{i+1}} \right\rfloor

这个公式的原理是， $\lfloor X/2^i \rfloor$ 算的是 $X$ 中包含的 $2^i$ 的倍数的数量，而 $2\lfloor X/2^{i+1} \rfloor$ 算的是 $X$ 中包含的 $2^{i+1}$ 的倍数的数量（乘以2）。两者相减，正好就分离出了第 $i$ 位的系数，也就是 0 或 1。就像猫咪从一堆毛线球里，只挑出特定颜色的那一颗，喵~

把它代入我们的求和式中：

\sum_{k=1}^{N} \text{bit}_i(kM) = \sum_{k=1}^{N} \left( \left\lfloor \frac{kM}{2^i} \right\rfloor - 2 \cdot \left\lfloor \frac{kM}{2^{i+1}} \right\rfloor \right)

= \left( \sum_{k=1}^{N} \left\lfloor \frac{kM}{2^i} \right\rfloor \right) - 2 \cdot \left( \sum_{k=1}^{N} \left\lfloor \frac{kM}{2^{i+1}} \right\rfloor \right)

看呐！问题现在变成了如何计算形如 $\sum_{k=1}^{N} \lfloor \frac{ak+b}{c} \rfloor$ 的和式。在这里， $a=M, b=0, c=2^i$ 或 $2^{i+1}$ 。

锵锵~ 这时候就要请出我们的秘密武器——类欧几里得算法 (Floor Sum Algorithm) 啦！它专门解决这种带下取整的求和问题，非常厉害的说！

一个计算 $F(a, b, c, n) = \sum_{k=0}^{n} \lfloor \frac{ak+b}{c} \rfloor$ 的类欧几里得函数 floor_sum(a, b, c, n) 通常通过递归实现：

基本情况: 如果 $a=0$ ，那么 $\lfloor \frac{b}{c} \rfloor$ 是个常数，总和就是 $(n+1) \cdot \lfloor \frac{b}{c} \rfloor$ 。
规约: 如果 $a \ge c$ 或 $b \ge c$ ，我们可以把 $a, b$ 对 $c$ 取模来简化问题。 $\lfloor \frac{ak+b}{c} \rfloor = \lfloor \frac{(a \pmod c)k + (b \pmod c)}{c} \rfloor + k \cdot \lfloor \frac{a}{c} \rfloor + \lfloor \frac{b}{c} \rfloor$ 求和后，后两项是等差数列求和和常数求和，可以 $O(1)$ 计算，问题规模被减小。
递归转换: 如果 $a < c$ 且 $b < c$ ，这是最核心的一步。令 $m = \lfloor \frac{an+b}{c} \rfloor$ ，可以证明（证明过程比较复杂，涉及到几何计数），原式可以转换为一个与原问题结构相同，但参数互换的新问题： $\sum_{k=0}^{n} \lfloor \frac{ak+b}{c} \rfloor = n \cdot m - \sum_{j=0}^{m-1} \lfloor \frac{cj+c-b-1}{a} \rfloor$ 这样 $a, c$ 的角色互换，就像欧几里得算法一样，参数规模会不断减小，最终达到基本情况。

我们的求和是从 $k=1$ 到 $N$ 的，而类欧模板通常是从 $k=0$ 到 $n$ 。不过没关系，因为当 $k=0$ 时， $\lfloor \frac{0 \cdot M + 0}{c} \rfloor = 0$ ，所以 $\sum_{k=1}^{N} = \sum_{k=0}^{N}$ 。我们可以直接调用 floor_sum(M, 0, c, N)。

总结一下我们的完整步骤:

初始化总答案 ans = 0。
遍历二进制位 $i$ 从 0 到 60 左右（因为 $N, M$ 在 long long 范围内）。
检查 $M$ 的第 $i$ 位是否为 1。
如果是 1，就利用类欧几里得算法计算：
- $S_1 = \text{floor\_sum}(M, 0, 2^i, N)$
- $S_2 = \text{floor\_sum}(M, 0, 2^{i+1}, N)$
- 第 $i$ 位的贡献次数为 $C_i = S_1 - 2 \cdot S_2$ 。
将 $C_i \cdot 2^i$ 累加到 ans 中，注意全程取模。
最后输出 ans 就好啦！

注意哦，在类欧几里得算法的计算过程中，像 a * n 这样的乘积可能会超过 long long 的范围，所以我们需要使用 __int128 来保证计算的精度，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码哦，希望能帮助到你，喵~

cpp

#include <iostream>

// 定义一些常量和类型别名，让代码更清晰~
using int128 = __int128;
using ll = long long;

const int MOD = 1e9 + 7;

// 快速幂函数，用来计算模逆元
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (int128)res * base % MOD;
        base = (int128)base * base % MOD;
        exp /= 2;
    }
    return res;
}

// 计算 a 在模 MOD 下的逆元
ll modInverse(ll n) {
    return power(n, MOD - 2);
}

const ll INV2 = modInverse(2);

// 类欧几里得算法核心函数，喵~
// 计算 sum_{k=0 to n} floor((a*k + b) / c)
ll floor_sum(ll a, ll b, ll c, ll n) {
    if (a == 0) {
        // a=0, 项为常数 floor(b/c)
        return (n + 1) % MOD * (b / c % MOD) % MOD;
    }
    if (a >= c || b >= c) {
        // 规约 a 和 b
        ll a_mod_c = a % c;
        ll b_mod_c = b % c;
        ll a_div_c = a / c;
        ll b_div_c = b / c;

        // 递归计算简化后的部分
        ll res = floor_sum(a_mod_c, b_mod_c, c, n);
        
        // 加上被分离出来的部分
        // 等差数列求和: sum_{k=0 to n} k = n(n+1)/2
        ll n_mod = n % MOD;
        ll sum_k_term = (a_div_c % MOD) * (n_mod * (n_mod + 1) % MOD) % MOD * INV2 % MOD;
        // 常数项求和: sum_{k=0 to n} 1 = n+1
        ll const_term = (b_div_c % MOD) * ((n + 1) % MOD) % MOD;
        
        res = (res + sum_k_term) % MOD;
        res = (res + const_term) % MOD;
        return res;
    }

    // 核心递归转换步骤
    int128 m_128 = (int128)a * n + b;
    ll m = m_128 / c;

    ll res = (n % MOD) * (m % MOD) % MOD;
    ll recursive_part = floor_sum(c, c - b - 1, a, m - 1);

    // 注意减法可能产生负数，要加上 MOD
    return (res - recursive_part + MOD) % MOD;
}

int main() {
    // 为了更快的输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    ll n, m;
    std::cin >> n >> m;

    ll total_sum = 0;

    // 遍历M的二进制位，从第0位到第60位
    for (int i = 0; i <= 60; ++i) {
        // 检查M的第i位是否为1
        if ((m >> i) & 1) {
            int128 c1 = (int128)1 << i;
            int128 c2 = (int128)1 << (i + 1);

            // 计算 sum floor(k*m / 2^i)
            ll sum1 = floor_sum(m, 0, c1, n);
            // 计算 sum floor(k*m / 2^(i+1))
            ll sum2 = floor_sum(m, 0, c2, n);

            // 第i位的贡献次数 = sum1 - 2 * sum2
            ll count = (sum1 - 2 * sum2 % MOD + 2 * MOD) % MOD;
            
            // 第i位的总贡献值
            ll bit_contribution = (count * (c1 % MOD)) % MOD;

            total_sum = (total_sum + bit_contribution) % MOD;
        }
    }

    std::cout << total_sum << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(\log(\max(N, M)))$ 主循环遍历了大约 60 个二进制位，这是一个常数。在循环内部，我们调用了类欧几里得函数 floor_sum(a, b, c, n)。该函数的复杂度与欧几里得算法（求最大公约数）类似，递归深度为 $O(\log a + \log c)$ 。在我们的调用中， $a=M, c=2^i$ 或 $2^{i+1}$ 。所以单次调用的复杂度是 $O(\log M + \log(2^i)) = O(\log M + i)$ 。总时间复杂度是 $\sum_{i=0}^{60} O(\log M + i)$ 。由于 $i$ 的最大值是常数 60，并且我们通常认为 $\log M$ 也和位数相关，所以整体复杂度可以近似看作是 $O(\text{bit\_count} \cdot \log(\max(N,M)))$ ，在 $N, M$ 为 long long 范围时，这非常快。
空间复杂度: $O(\log(\max(N, M)))$ 空间主要消耗在 floor_sum 函数的递归调用栈上。递归的深度是 $O(\log M + i)$ ，所以空间复杂度与时间复杂度中的对数部分成正比。

知识点总结

位运算分解: 遇到涉及位运算 &, |, ^ 的求和问题，一个非常强大的思想是按位独立计算贡献。将整体的求和问题分解为对每一位的贡献求和。
提取特定位: 公式 $\text{bit}_i(X) = \lfloor \frac{X}{2^i} \rfloor - 2 \cdot \lfloor \frac{X}{2^{i+1}} \rfloor$ 是一个从数值中分离出特定二进制位的精妙技巧，值得牢记于心！
类欧几里得算法: 这是解决一类特定形式的求和问题的模板算法，即 $\sum \lfloor \frac{ak+b}{c} \rfloor$ 。它的核心思想是通过类似欧几里得算法的递归和规约，不断减小问题规模。
__int128 的使用: 在处理可能超过 long long（ $2^{63}-1$ ）范围的整数运算时，__int128 是一个非常有用的工具，可以避免溢出导致的错误。喵~ 记得要用 __int128 哦，不然数字太大会溢出，就像小猫咪的碗装不下太多小鱼干一样！

希望这篇题解能帮助你理解这道有趣的题目！继续加油哦，主人！喵~

KM and M - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​