题解 CF2039C1

HYdroKomide · 2024-12-04 09:53:59 · 题解

题意：

在区间 [1,m] 中，有多少个数 y 使得 x\oplus y 是 x 或 y 的因数。

思路：

发现 x 的范围并不大。而且我们有一个显而易见的性质：当 x\neq0 且 y 的二进制最高位大于 x 时，x\oplus y 一定大于 x 且小于 y\times 2（当然也不会等于 y），条件不可能满足。

因此，只需要枚举 1 到 x\times 2 的所有数，判断是否满足条件即可。

程序如下：

#include<cstdio>
#include<vector>
using namespace std;
const int N=5e5+5;
int T;
int main(){
    scanf("%d",&T);
    while(T--){
        int x,ans=0;
        long long m;
        scanf("%d%lld",&x,&m);
        for(int i=1;i<=m&&i<=(x<<1);i++){
            if(i==x)continue;
            int res=x^i;
            if(i%res==0||x%res==0)ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

THE END