把 popcount 按位拆成 floor 差分,用类欧几里得在 O(log) 内求出每位的 1 的个数,全程 __int128 防溢出。
OJ: roj
题目 ID: 1805
难度:提高+/省选-
标签:数学类欧几里得位运算python
创建: 2026-10-08 04:20
更新: 2026-10-08 04:20
形式化题目
给出等差数列的末项偏移
记
共有
由范围可知最大项
正解
思路
朴素做法。 逐项求出
观察一:按位拆分。 一个数
对整列求和,位与位之间互不干扰,答案就是各位贡献之和:
因为最大项小于
观察二:
其中定义通用和式
它的几何意义是直线
观察三:
情况 A:
对
情况 B:
推导要点:
汇总。 每组数据枚举
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:单次
的递归深度为 , 每组数据枚举至多 个二进制位,故单组 ,即常数级; 总时间 ,实测 20 组顶格数据远低于 1 ms。 - 空间:递归深度不超过
层, ,可视为 。 - 与 C++ 解法的关系:
main.cpp与main.py是同一算法。 两者的唯一差别是整数宽度:、 、 这些中间量 会达到 量级,C++ 必须用 __int128(long long只有约), 而 Python 的整数天然任意精度,不需要额外处理,也不需要担心 之类的移位溢出。
总结
- "数
的个数"总是先想按位拆: 把 popcount 变成两个 floor 之和的差, 才可能上数据结构或数论算法。 只差一个 :数列是等差数列, 恒定不变, 这也是可以复用同一套类欧几里得代码的原因。 - 类欧几里得就是"取模 + 坐标轴转置"交替:斜率大就拆整数部分(取模),
斜率小于
就转置坐标轴(把 与 互换),两个动作轮流把参数压到对数级。 - 溢出是本题的头号实现坑:
、 时, 级别为 ,C++ 必须 __int128全程参与运算; Python 无此问题,但要注意别用float。 - 该素材源自带数据生成脚本(
data.py/gen.*),说明测试数据是自造的, 题面也属于网络重建(同名原题见 JZOJ 3492 /【NOIP2013模拟联考12】数数)。 因此本解以题面给出的范围为唯一依据,验证只保证"样例 + 仓库 data/ 全过", 不代表官方数据通过。