P8177题解

· · 题解

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

\because$ 设 $a_i=a_0+d \times i $\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$ 同理可知，在 $[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;
}