BZOJ2118: 墨墨的等式 思维建图

• muyangshaonian 发布于
• 984 收藏

问a1x1+a2x2+a3x3+……+anxn∈[Bmin,Bmax]中的非负整数解有多少组 由于是非负所以不能简单求gcd，可以考虑任取其中某一项ax， 以它的模域0-ax-1建图，单向通过a数组转移，这样跑出从模0到模任意数的最短路 最短是为了保证在BminBmax里能塞进最多的ax 显然ax取最小可以让复杂度最好，实测取max是min耗时2倍 正确性就是如果m可以取到，那么k*ax+m都可以...