自动搬运

查看原文

来自洛谷，原作者为

	lichengyun 这个家伙是个废物

搬运于2025-08-24 22:36:38，当前版本为作者最后更新于2022-03-04 09:54:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本蒟蒻提供一种单组询问 $\Theta(1)$ 的解法。

$\because$ 设 $a_i=a_0+d \times i$

$\therefore {a}$ 为等差数列。

$\because a_i < \frac{a_i+a_{i+1}}{2} < a_{i+1}$

由对称性，我们只考虑区间 $[a_0,a_1)$。

令 $b_1=a_0+\frac{d}{2}$

$\therefore$ 故 $b_1$ 可以由 $\frac{a_0+a_1}{2}$ 得到。

$\therefore$ 同理可知，在 $[a_0,a_1)$ 中可取的全部数为 $a_0,a_0+\frac{d}{2^i},a_0+ \frac{2d}{2^i},\cdots,a_0+\frac{(2^{i}-1)d}{2^i}$

($i$ 为整除 $d$ 的最大 $2^p (p \in \mathrm{N}$))

综上，最多可添加 $(n-1)\times (\operatorname{lowbits}(d)-1)$个数。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int T,n,a,d;
    //I/O流优化
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>T;
    while(T--){
        cin>>n>>a>>d;
        cout<<(1ll*(n-1)*((d&(-d))-1))<<endl;
    }
    return 0;
}