题解：P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目

· · 题解

P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目

首先我们观察这个样例，发现 11 是最后一个模 3 余 2 的数，而且今后所有这样的数都可以通过将一个 3 的倍数中删去 4 个 3，加上 2 个 7 得到。

初步猜测，我们需要解决一个方程类似这样（设 a\lt b）：

by-ax=k

其中 x,y 均为正整数，k\lt a。则对于一个 k，使得这个方程的最小正整数解的 x,y 最大，即可以构造答案为 a(x-1)+k。由此可得 O(V) 做法。

考虑优化，将 b 看做 ax'+y'，其中 y'\lt a。

则原式子可以化成：

(ax'+y')y-ax=k (x'y-x)a+y'y=k y'y\equiv k\pmod a

此时容易构造最大的 y 为 a-1（因为 y' 和 k 互质）。

容易反推出 k,x，计算答案。复杂度 O(1)