ALL：6
AC：3
补题：1

D. ConstructOR

题意：

给定正整数 a,b,da,b,da,b,d，求一个正整数 xxx 使得 d∣(aor⁡x)d\mid(a\operatorname{or}x)d∣(aorx) 且 d∣(bor⁡x)d\mid(b\operatorname{or}x)d∣(borx)，其中 or⁡\operatorname{or}or 表示按位或运算。

思路：考虑最简单的情况： a∣xa|xa∣x 与 b∣xb|xb∣x 相等。问题可以转化为找到一个 xxx ，使得两个式子成立：

1. x≡a∣b(mod230)x\equiv a|b \pmod {2^{30}}x≡a∣b(mod230)

2. x≡0(modd)x\equiv 0\pmod dx≡0(modd)

这个问题可以用拓展中国剩余定理解决，详见 博客 。列出不定方程，联立并用 exgcd 求解。联立出的不定方程为 230⋅k1−d⋅k2=−(a∣b)2^{30}\cdot k_1-d\cdot k_2=-(a|b)230⋅k1​−d⋅k2​=−(a∣b) ，求特解并偏移即可。

注意一个 exgcd 的坑，传入的系数 a,b>0a,b>0a,b>0 才行，如果传入系数 <0<0<0 ，求出来的特解不正确。因此形如 a⋅x−b⋅y=c(a,b>0)a\cdot x-b\cdot y=c(a,b>0)a⋅x−b⋅y=c(a,b>0) 的不定方程可以转化为 a⋅x+b⋅(−y)=ca\cdot x+b\cdot(-y)=ca⋅x+b⋅(−y)=c 然后求解。

AC代码：https://codeforces.com/contest/1748/submission/182418468