非負整数 \(x\) の popcount は、次のようにして求めることもできます。

\[x-\sum _ {i=1} ^ \infty \left\lfloor\dfrac x{2 ^ i}\right\rfloor\]

この式を用いると、floor sum を計算する回数を公式解説の半分程度にすることができます。

これは、いくつかの方法で示すことができます。 たとえば、公式解説の式 \(\displaystyle\left\lfloor\dfrac{x+2 ^ k}{2 ^ {k+1}}\right\rfloor-\left\lfloor\dfrac{x}{2 ^ {k+1}}\right\rfloor\) を変形する方針でも示すことができます。

\[\begin{aligned} \left\lfloor\dfrac{x+2 ^ k}{2 ^ {k+1}}\right\rfloor-\left\lfloor\dfrac{x}{2 ^ {k+1}}\right\rfloor&=\left\lfloor\dfrac{S+1}{2}\right\rfloor-\left\lfloor\dfrac{S}{2}\right\rfloor\quad\left(S=\left\lfloor\dfrac{x}{2 ^ k}\right\rfloor\right)\\ &=\left\lceil\dfrac{S}{2}\right\rceil-\left\lfloor\dfrac{S}{2}\right\rfloor\\ &=\left(S-\left\lfloor\dfrac{S}{2}\right\rfloor\right)-\left\lfloor\dfrac{S}{2}\right\rfloor\\ &=S-2\left\lfloor\dfrac{S}{2}\right\rfloor\\ &=\left\lfloor\dfrac{x}{2 ^ k}\right\rfloor-2\left\lfloor\dfrac{x}{2 ^ {k+1}}\right\rfloor \end{aligned}\]

なので、これを \(k=0,1,\ldots\) について足し上げることで上の式が得られます。

実装例は以下のようになります。

#include <iostream>
#include <atcoder/math>

using namespace std;

int main() {

    int T;
    cin >> T;

    for (int testcase = 0; testcase < T; ++testcase) {
        long N, M, R;
        cin >> N >> M >> R;
        long n{(N - R) / M + 1}; // floor sum の上限

        // 答えの計算
        auto ans{n * R + n * (n - 1) / 2 * M};
        for (int i = 2; i <= N; i *= 2)
            ans -= atcoder::floor_sum(n, i, M, R);
        cout << ans << ' ';
    }

    return 0;
}