【11.12】Codeforces Round #833 (Div. 2)

ALL：6
AC：3
补题：1

---

D. ConstructOR

题意：

给定正整数 $a,b,d$，求一个正整数 $x$ 使得 $d\mid (a\mathrm{or}x)$ 且 $d\mid (b\mathrm{or}x)$，其中 $\mathrm{or}$ 表示按位或运算。

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

1. $x\equiv a|b(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{30})$

2. $x\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}d)$

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

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

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