20220911 CCPC 网络赛

第一次正式参加 xcpc 比赛，三个人都好久没写代码了，导致一堆题写出来了没调出来，很下饭。

A Doubt vs Lie

模拟题，直接模拟题意即可。

C Guess

手玩一下找下规律即可。

H Mutiple Set

记 \(l=\lceil \frac L x\rceil,r=\lfloor \frac R x\rfloor\) ，则需要解方程 \(2^{r-l+1}\cdot x\cdot (l+r)\cdot (r-l+1)=K\) 。利用 Pollard-rho 算法处理出 \(K\) 的质因数分解情况，再枚举 \(K\) 的每个质因子作为 \(x\) 验证以上等式是否成立。

由于 \(K\le 10^{14}\) ，故大于 \(10^7\) 的质因子至多只会有一个，于是也可以先筛出 \(10^7\) 以内的所有质数，利用这些质数即可对 \(K\) 完成质因子分解。

K Roulette

5000 次都输的概率是很低的，于是我们可以用一个经典策略：第 \(i\) 次押 \(2^i\times y\) 元，只要赢一次就可以把前面投的钱全部赢回来，并且额外获得 \(y\) 元。