首页 " 解题报告 " 正文
30 + 0 + 0,rk 38,暴力写挂.
首先我们考虑证明一个东西,即原问题有解当且仅当 \gcd(x,y) | k,x + y \geq k.
我们考虑构造一个操作序列来满足上述条件,设 x< y.
如果我们把 x 倒 k 桶进 y 使得溢出,那么我们此时得到的就是 kx\bmod y,所以我们这里就可以构造出任何一个 [0,y-1] 水量的桶,所以构造 [x,x+y-1] 同样是简单的.
所以我们考虑就是要统计满足下列两个条件的 (x,y) 对数:
\gcd(a_x,a_y) | k
a_x + a_y \geq k
k = 1 的情况是 trivial 的,我们考虑就是求两个数