最小的 $x$ 满足 $L\le x\bmod P\le R$

发布时间 2023-11-16 22:40:43作者: CharlieVinnie

\(G(L, R, D, P)\)\(y P+L \leq x D \leq y P+R\) ,满足 \(1 \leq L \leq R<P, D<P\) ,其中 \(x\) 的最小非负整数解。

这是一个模板题,题号是 POJ 3530,但肯定没多少人见过,这也算是一种类欧几里得算法吧。

  • 首先若 \(D=0\) 那么显然就无解。
  • 否则假设 \(P=0\), 这时候有解,就直接输出 (此时肯定是最小值,若 \(P>0\), 那么 \(x\) 的区间会变大)
  • 否则 \(P>0\) ,由于上面找不到解 ( \(L, R\) 中间没有 \(D\) 的倍数),一定有 \(m D<L \leq R<(m+ 1) D\) ,这样我们就成功的把值域压到的 \(D\) 的同一段! 移项有 \(x D-R \leq y P \leq x D-L\) ,所以此时问题转化为了 \(G(-R \bmod D,-L \bmod D, P \bmod D, D)\) 。这里可以模的基础也是, \(L, R\) 的区间限制压到了同一段,而 \(P\) 单点的模是没有影响的。

复杂度显然由后两个参数 \((D,P)\rightarrow (P\bmod D,D)\) 确定。

拜谢 Remake