Codeforces Round #730 ABCD 题解 (Java/C++)

A. Exciting Bets

题解

如果两个数相同，那么显然答案是无穷大。

如果两个数不同，那么可以令两个数为a和a+x。在执行若干操作后，两个数分别为a+y和a+y+x。
设操作后的最大公约数为q。则有$a+y\equiv 0\pmod q$且$a+y+x\equiv 0\pmod q$。进而有$x\equiv 0\pmod q$。
于是有$q\leq x$。因为最坏的场景下两个数可以变成0和x。因此两个数不同的时候，最大公约数必为x。

于是我们只需要寻找a附近的x的倍数即可。

代码

Java

C++

B. Customising the Track

题解

显然，均分即可。假设均分的余数为x，于是n条路中有x条路多1辆车。因此最终结果为$x\cdot (n-x)$。

代码

Java

C++

C. Need for Pink Slips

题解

递归暴力模拟即可。虽然输入的概率可以有4位小数，但是由于v最小是0.1，因此最多有10层递归。

代码

Java

C++

D. RPD and Rap Sheet (Easy/Hard)

题解

首先我们发现，异或操作满足：若$a\oplus b=c$则$c\ominus a=b$。

假设初始密码为x。经历过若干查询之后，当前的密码其实是可以推导出来的。设第i次查询的内容为$q_i$，查询后的密码为$x_i$，则有$$\begin{equation*}
x\oplus x_1=q_1\\
x_1\oplus x_2=q_2\\
x_2\oplus x_3=q_3\\
...\\
\end{equation*}$$

于是我们可以从0开始依次枚举初始密码，根据我们假设的初始密码，推导出当前的密码，并且查询即可。
以第4次查询为例，我们假设的初始密码是3。则当前的密码是$q_3 \ominus q_2 \oplus q_1 \ominus 3$。
以第5次查询为例，我们假设的初始密码是4。则当前的密码是$q_4 \ominus q_3 \oplus q_2 \ominus q_1 \oplus 4$。

代码

Java

C++