数数

GitHub跳转原题关系图返回列表

把 popcount 按位拆成 floor 差分,用类欧几里得在 O(log) 内求出每位的 1 的个数,全程 __int128 防溢出。

OJ: roj

题目 ID: 1805

难度:提高+/省选-

标签:数学类欧几里得位运算python

创建: 2026-10-08 04:20

更新: 2026-10-08 04:20

形式化题目

给出等差数列的末项偏移 BB、公差 AA 与项数 NN,数列的第 ii 项为

xi=B+i⋅A,i=1,2,…,N.x_i = B + i \cdot A, \qquad i = 1, 2, \dots, N .

记 popcount⁡(x)\operatorname{popcount}(x) 为 xx 的二进制表示中 11 的个数,求

S=∑i=1Npopcount⁡(xi).S = \sum_{i=1}^{N} \operatorname{popcount}(x_i).

共有 TT 组询问,每组给出 A,B,NA, B, N:

1⩽T⩽20,1⩽A⩽104,1⩽B⩽1016,1⩽N⩽1012.1 \leqslant T \leqslant 20, \quad 1 \leqslant A \leqslant 10^4, \quad 1 \leqslant B \leqslant 10^{16}, \quad 1 \leqslant N \leqslant 10^{12}.

由范围可知最大项 B+N⋅A⩽1016+1012×104=2×1016<255B + N \cdot A \leqslant 10^{16} + 10^{12} \times 10^4 = 2 \times 10^{16} < 2^{55}, 即所有数都落在 5555 个二进制位以内。

正解

思路

朴素做法。 逐项求出 B+i⋅AB + i\cdot A,用二进制计数函数累加。单组 O(N)O(N), 而 NN 可达 101210^{12},限时 10001000 ms 下最多跑 10810^8 量级,必然超时。 瓶颈在于"逐项"——必须改成"按位整体统计"。

观察一:按位拆分。 一个数 xx 的第 kk 位是不是 11,取决于 ⌊x/2k⌋\lfloor x / 2^k \rfloor 的奇偶性。利用向下取整,可以把这一位的取值写成一个精确的差分:

bit⁡k(x)=⌊x2k⌋−2⌊x2k+1⌋∈{0,1}.\operatorname{bit}_k(x) = \left\lfloor \frac{x}{2^k} \right\rfloor - 2 \left\lfloor \frac{x}{2^{k+1}} \right\rfloor \in \{0, 1\}.

对整列求和,位与位之间互不干扰,答案就是各位贡献之和:

Sk=∑i=1N⌊B+i⋅A2k⌋,S=∑k⩾0(Sk−2 Sk+1).S_k = \sum_{i=1}^{N} \left\lfloor \frac{B + i\cdot A}{2^k} \right\rfloor, \qquad S = \sum_{k \geqslant 0} \left( S_k - 2\,S_{k+1} \right).

因为最大项小于 2552^{55},kk 只需枚举到 2k>B+N⋅A2^k > B + N\cdot A 为止,至多 5555 个非零项。 问题于是化为:怎样快速求出 SkS_k?

观察二:SkS_k 是类欧几里得能处理的形状。 把下标平移一下:

Sk=∑i=1N⌊A⋅i+B2k⌋=∑j=0N−1⌊A⋅j+(A+B)2k⌋=f ⁣(A,  A+B,  2k,  N−1),S_k = \sum_{i=1}^{N} \left\lfloor \frac{A\cdot i + B}{2^k} \right\rfloor = \sum_{j=0}^{N-1} \left\lfloor \frac{A\cdot j + (A + B)}{2^k} \right\rfloor = f\!\left(A,\; A+B,\; 2^k,\; N-1\right),

其中定义通用和式

f(a,b,c,n)=∑i=0n⌊a⋅i+bc⌋.f(a, b, c, n) = \sum_{i=0}^{n} \left\lfloor \frac{a \cdot i + b}{c} \right\rfloor .

它的几何意义是直线 y=ax+bcy = \dfrac{a x + b}{c} 在 x∈[0,n]x \in [0, n] 上盖住的整点个数 (含边界,取直线下方/线上的整点)。注意 SkS_k 中 a=Aa = A 固定,只有 c=2kc = 2^k 在变, 所以每组数据的 5555 次调用共享同一个 aa。

观察三:ff 的化简与辗转相除同构。 分两种情况。

情况 A:a⩾ca \geqslant c 或 b⩾cb \geqslant c。 把整除部分直接拆出来:

⌊ai+bc⌋=⌊ac⌋i+⌊bc⌋+⌊(a mod c) i+(b mod c)c⌋,\left\lfloor \frac{a i + b}{c} \right\rfloor = \left\lfloor \frac{a}{c} \right\rfloor i + \left\lfloor \frac{b}{c} \right\rfloor + \left\lfloor \frac{(a \bmod c)\, i + (b \bmod c)}{c} \right\rfloor,

对 i=0..ni = 0..n 求和即得

f(a,b,c,n)=n(n+1)2⌊ac⌋+(n+1)⌊bc⌋+f(a mod c,  b mod c,  c,  n).f(a, b, c, n) = \frac{n(n+1)}{2}\left\lfloor \frac{a}{c} \right\rfloor + (n+1)\left\lfloor \frac{b}{c} \right\rfloor + f(a \bmod c,\; b \bmod c,\; c,\; n).

情况 B:a<ca < c 且 b<cb < c。 此时斜率小于 11,改用转置坐标轴计数: 把"对每个 xx 数 yy 的下方整点"换成"对每个 yy 数 xx 的右侧整点",用补集相减即可得到

f(a,b,c,n)=n⋅m−f ⁣(c,  c−b−1,  a,  m−1),m=⌊an+bc⌋.f(a, b, c, n) = n \cdot m - f\!\left(c,\; c - b - 1,\; a,\; m - 1\right), \qquad m = \left\lfloor \frac{a n + b}{c} \right\rfloor .

推导要点:mm 是最大纵坐标,若 m=0m = 0 则一个整点都没有,直接返回 00; 否则在矩形 [0,n]×[1,m][0, n] \times [1, m] 中,直线严格上方的整点数可用"总数减下方数"算出, 再换成 yy 为自变量、xx 为因变量后,系数 (c,a)(c, a) 互换,其中 −1-1 来自严格不等号 到非严格不等号的边界调整。这一步把 cc 与 aa 的角色对调, 下一次递归必然进入情况 A 并对新 cc 取模,因此参数按 c mod ac \bmod a 的速度衰减, 递归深度为 O(log⁡max⁡(a,c))O(\log \max(a, c))——这正是"类欧几里得"的名字来源。

汇总。 每组数据枚举 k=0,1,…k = 0, 1, \dots(2k⩽B+N⋅A2^k \leqslant B + N\cdot A), 累加 f(A,A+B,2k,N−1)−2f(A,A+B,2k+1,N−1)f(A, A+B, 2^k, N-1) - 2 f(A, A+B, 2^{k+1}, N-1) 即可。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 04:20
# update_at: 2026-10-08 04:20

import sys

# 值域上界:数列最大项 <= 1e16 + 1e12 * 1e4 = 2e16 < 2^55,所以只需枚举 55 个二进制位


def floor_sum(a: int, b: int, c: int, n: int) -> int:
    """Σ_{i=0}^{n} floor((a*i + b) / c),类欧几里得递归,规模对数级衰减。"""
    if a == 0:
        return b // c * (n + 1)                      # 水平线,直接算
    if a >= c or b >= c:                             # 拆出斜率/截距的整数部分
        return (floor_sum(a % c, b % c, c, n)
                + n * (n + 1) // 2 * (a // c)
                + (n + 1) * (b // c))
    max_y = (a * n + b) // c                         # 斜率 < 1,转置坐标轴
    if max_y == 0:
        return 0
    return n * max_y - floor_sum(c, c - b - 1, a, max_y - 1)


def count_ones(a: int, b: int, n: int) -> int:
    """一组询问的答案:逐位累加等差数列各项二进制中该位为 1 的个数。"""
    limit = b + a * n                                # 数列最大项,决定枚举到哪一位
    ans = 0
    power = 1                                        # power = 2^k,即当前位的位权
    while power <= limit:
        # 第 k 位上 1 的个数 = Σ floor(x / 2^k) - 2 * Σ floor(x / 2^{k+1})
        ones_here = (floor_sum(a, a + b, power, n - 1)
                     - 2 * floor_sum(a, a + b, power * 2, n - 1))
        ans += ones_here
        power *= 2
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)
    out: list[str] = []

    for _ in range(T):
        a, b, n = next(data), next(data), next(data)
        out.append(str(count_ones(a, b, n)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 04:20
 * update_at: 2026-10-08 04:20
 */
// 一本通 1805《数数》:统计等差数列 B+A, B+2A, ..., B+N*A 共 N 项
// 的二进制表示中 1 的总个数,T 组询问。
//
// 核心:按二进制位拆分贡献。第 k 位是否为 1 可用
//   bit_k(x) = floor(x / 2^k) - 2 * floor(x / 2^{k+1})
// 精确表示,于是答案 = Σ_k ( S_k - 2 * S_{k+1} ),
// 其中 S_k = Σ_{i=1}^{N} floor((B + i*A) / 2^k) = f(A, A+B, 2^k, N-1)。
// f 用类欧几里得(辗转相除式)递归在 O(log) 内求出。
#include <cstdio>

typedef long long ll;
typedef __int128 i128;

// f(a, b, c, n) = Σ_{i=0}^{n} floor((a*i + b) / c),要求 a,b,c >= 0,n >= 0。
// 每层递归都对 c 取模,规模呈对数级衰减,递归深度 O(log c)。
i128 floor_sum(i128 a, i128 b, i128 c, i128 n) {
    if (a == 0) return (b / c) * (n + 1);                        // 水平线,直接算
    if (a >= c || b >= c) {                                      // 拆出整除部分
        return floor_sum(a % c, b % c, c, n)
             + n * (n + 1) / 2 * (a / c)
             + (n + 1) * (b / c);
    }
    i128 max_y = (a * n + b) / c;                                // 斜率 < 1,转置坐标轴
    if (max_y == 0) return 0;                                    // 一格都数不到
    return n * max_y - floor_sum(c, c - b - 1, a, max_y - 1);
}

// 输出 __int128(答案最大约 5.5e13,但中间量到 1e28,故统一用 128 位)
void print_i128(i128 x) {
    if (x == 0) { putchar('0'); return; }
    char buf[64];
    int len = 0;
    // 这里必须把 __int128 窄化成 int 才能做字符运算,属于对内存类型的必要转换
    while (x > 0) { buf[len++] = '0' + int(x % 10); x /= 10; }
    while (len > 0) putchar(buf[--len]);
}

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T--) {
        ll A, B, N;
        scanf("%lld %lld %lld", &A, &B, &N);
        ll limit = B + A * N;            // 数列最大项,<= 2e16 < 2^55,ll 不会溢出
        i128 ans = 0;
        for (ll power = 1; power <= limit; power *= 2) {
            // S_k = Σ_{i=1}^{N} floor((B + i*A) / 2^k)
            i128 sum_low = floor_sum(A, A + B, power, N - 1);
            i128 sum_high = floor_sum(A, A + B, power * 2, N - 1);
            ans += sum_low - 2 * sum_high;   // 第 k 位上 1 的出现次数
        }
        print_i128(ans);
        putchar('\n');
    }
    return 0;
}

复杂度

  • 时间:单次 ff 的递归深度为 O(log⁡max⁡(a,c))=O(55)O(\log \max(a, c)) = O(55), 每组数据枚举至多 5555 个二进制位,故单组 O(552)O(55^2),即常数级; 总时间 O(T⋅log⁡2(值域))O(T \cdot \log^2(\text{值域})),实测 20 组顶格数据远低于 1 ms。
  • 空间:递归深度不超过 5555 层,O(log⁡(值域))O(\log(\text{值域})),可视为 O(1)O(1)。
  • 与 C++ 解法的关系:main.cpp 与 main.py 是同一算法。 两者的唯一差别是整数宽度:n(n+1)/2n(n+1)/2、a⋅n+ba\cdot n + b、n⋅mn \cdot m 这些中间量 会达到 102410^{24} 量级,C++ 必须用 __int128(long long 只有约 1.8×10191.8 \times 10^{19}), 而 Python 的整数天然任意精度,不需要额外处理,也不需要担心 1≪311 \ll 31 之类的移位溢出。

总结

  • "数 11 的个数"总是先想按位拆:bit⁡k(x)=⌊x/2k⌋−2⌊x/2k+1⌋\operatorname{bit}_k(x) = \lfloor x/2^k \rfloor - 2\lfloor x/2^{k+1} \rfloor 把 popcount 变成两个 floor 之和的差,∑⌊⋅⌋\sum \lfloor \cdot \rfloor 才可能上数据结构或数论算法。
  • SkS_k 只差一个 c=2kc = 2^k:数列是等差数列,a=Aa = A 恒定不变, 这也是可以复用同一套类欧几里得代码的原因。
  • 类欧几里得就是"取模 + 坐标轴转置"交替:斜率大就拆整数部分(取模), 斜率小于 11 就转置坐标轴(把 cc 与 aa 互换),两个动作轮流把参数压到对数级。
  • 溢出是本题的头号实现坑:N⩽1012N \leqslant 10^{12}、B⩽1016B \leqslant 10^{16} 时, n(n+1)/2n(n+1)/2 级别为 102410^{24},C++ 必须 __int128 全程参与运算; Python 无此问题,但要注意别用 float。
  • 该素材源自带数据生成脚本(data.py / gen.*),说明测试数据是自造的, 题面也属于网络重建(同名原题见 JZOJ 3492 /【NOIP2013模拟联考12】数数)。 因此本解以题面给出的范围为唯一依据,验证只保证"样例 + 仓库 data/ 全过", 不代表官方数据通过。