思路与算法

第k位的值等于floor(v/2^k)−2floor(v/2^(k+1))。对等差项v=B+A(i+1)累加，可化为两个floor_sum。用欧几里得式整商拆分：先取a/m与b/m产生的确定贡献，再把剩余格点三角形转置，交换m与a继续。最大项≤2×10^16，枚举k0..54足够。

正确性说明

整数除2^k的商的奇偶性恰是第k位，因此逐位floor差恒等式正确。floor_sum先拆出a,b中的整倍m，剩余0≤a,b<m；将格点y≤(ai+b)/m按纵坐标而非横坐标计数，可转为更小模数的同类和，欧几里得交换不改变总数。累加所有足够高位的贡献，恰得到全部二进制1数量。

复杂度

每个floor_sum欧几里得迭代O(log max(A,2^55))，55位各两次，总O(55 log2^55)，每组额外O(1)空间，T组乘T；初始化与读入O(T)。

易错点

原数列从B+A而非B开始；floor_sum范围为i0..N−1，所以偏移应是B+A。中间商和可大于64位，使用128位；最终1的总数≤55N，64位足够。最高有效位不超过54。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using u128 = __uint128_t;
u128 fs(ull n, ull m, ull a, ull b) {
    u128 ans = 0;
    while (true) {
        if (a >= m) {
            ans += (u128)n * (n - 1) / 2 * (a / m);
            a %= m;
        }
        if (b >= m) {
            ans += (u128)n * (b / m);
            b %= m;
        }
        ull y = a * n + b;
        if (y < m)
            break;
        n = y / m;
        b = y % m;
        swap(m, a);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ull a, b, n;
        cin >> a >> b >> n;
        ull ans = 0;
        for (int k = 0; k < 55; k++) {
            ull m = 1ULL << k;
            ans += (ull)(fs(n, m, a, b + a) - 2 * fs(n, m * 2, a, b + a));
        }
        cout << ans << '\n';
    }
}