题解：P16337 「ALFR Round 10」Bit Problem

fish_love_cat · 2026-04-19 21:08:46 · 题解

这场真不是红红橙橙黄？这场真不是红红橙橙黄？这场真不是红红橙橙黄？

特判 m=0。

于是 m>0，于是 n-m<n。

假设 n \operatorname{and} x=n，显然 x 拥有所有 n 拥有的二进制位，也就是说 x\ge n。

所以 n\operatorname{and}(n-m)<n。

于是每次操作 \text{popcount}(n) 都会减少。

当 n=0 的时候答案肯定就是 0 了。

直接模拟时间复杂度是 O(\log n) 的。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m,k;
        cin>>n>>m>>k;
        if(m==0){
            cout<<n<<'\n';
            continue;
        }
        while(k--&&n)n=n&max(n-m,0);
        cout<<n<<'\n';
    }
    return 0;
}
//「是的。因此，〈沉滞的第十一兽〉的名字当然也有其意义。
// Croyance，『坚定不移的信赖』
// ……不过，这个词或许本来应该解释为『信仰』会比较好。」