QOJ #11549. Inverse Knapsack

Statement

$t$ 次询问，每次给定素数 $p$ 和整数 $x$，要求构造一个 $[5000]$ 的子集 $s$ 满足 $\lvert s\rvert\leq150$ 且 $s$ 的倒数和与 $x$ 模 $p$ 同余。

$t\leq 10^3,\;10^8\leq p\leq 10^{18}$。

Solution

模 $p$ 同余看起来就没什么道理，直接选择若干个小素数使得其乘积不小于 $p-1$，那我们做一个分数分解状物可以分解到若干个形如 $\frac{a}{b}$ 之和，其中 $b$ 是你选的小素数之一，且 $\lvert a\rvert\leq b$。但是很遗憾你只能让分子取 $0,1$，那怎么办呢？

你发现可以决策 $0,1$ 启示你使用二进制，要求小素数不能选择 $2$，然后同除 $2^k$ 满足 $2^k$ 大于最大的选择的小素数，变成 $\frac{a}{2^kb}$，然后就可以用 $\frac{1}{2b},\frac{1}{2^2b},\cdots,\frac{1}{2^kb}$ 拼出来 $\frac{a}{2^kb}$ 了，但是这里只能处理 $a$ 是正数的情况，所以你先使用一下每个 $\frac{1}{b}$，再进行这个构造，$a<0$ 时就把对应的 $\frac{1}{b}$ 删了使得 $a\leftarrow a+2^k$ 即可。

恰当选择下小素数可以在本题中做到 $\lvert s\rvert\leq84$。