一开始在扩展gcd上想了许久没有办法将得出的数字直接转换成为相应的输出,后来发现就是模方程。
因为不求最佳解,所以直接使用ca*x = n (mod cb)即可。这个方程的解可以覆盖全部的n,因为该方程如果有解,则n是gcd(ca, cb)的倍数。因为ca, cb互质 gcd (ca, cb) = 1,所以明显通过单纯的加满B,向A中倒,然后清空A就可以遍历所有n的解(尽管可能不是最佳解)。
不能是cb*x = n (mod ca),因为n可能大于ca.
如果求最佳解,显然是bfs。当然这到题目也可以dfs来做,不过明显要复杂很多。