CF1748D ConstructOR 题解

jiangtaizhe001 · 2022-11-13 18:00:36 · 题解

可能更好的阅读体验

题目传送门

题目大意

给定 a,b,d，要求找到一个 0\le x\le 2^{60}，满足 a|x,b|x 都是 d 的倍数（| 代表按位或）。

题目解析

乍一看没什么思路，赛时想了很久才做出来。

显然当 a,b 的最低位的 1 比 d 的最低位还要低的时候，无解。
首先我们发现要让两个数字都是 d 的倍数就很麻烦，所以我们可以试着让这两个数字变成一个数字。
设 c=a|b，那么其实只要让 x|c=x 并且 x 是 d 的因数就可以了。
因为 x|c=x，所以不难发现 x 的一些位必定为 1。
从低位到高位考虑 x 的每一个限制。如果当前 x 的这一位是 0，但是 c 的这一位是 1，那么我们就把 d 的最低位的 1 通过移位操作和这一位对齐，然后加上移位后的数字，这样这一位就是 1 了。
因为 a,b,d\le 2^{30} 所以这样构造出来的 x 满足 x\le(a|b)\times d\le 2^{60}，一定合法。
时间复杂度 O(\log a)

ll a,b,c,d,ans; int cnt;
void work(){
    a=read(); b=read(); c=a|b; d=read(); ans=0; int i;
    cnt=0; for(i=0;i<30;i++) if(d&(1<<i)){ cnt=i; break; }
    for(i=0;i<30;i++) if((c&(1<<i))&&!(ans&(1<<i))){
        if(i<cnt){ puts("-1"); return; }
        ans+=(d<<(i-cnt));
    } print(ans),pc('\n'); assert((a|ans)%d==0&&(b|ans)%d==0); return;
}