上午又离线了捏?数论和博弈论完全听不懂哈哈，做题直接开赫！
下午赫题解去了。晚上买了包薯片吃??话说好久没吃薯片了捏，于是就和恋恋一起吃了薯片。同时见识到了XZT出生的一面?，依旧建议就地枪决捏。
明天就是庭哥讲课了???，haosen的课今天听了下，非常好haose。
另报：OP被封了。已告诉wyy???，就看省一生们什么时候回来了。计划生倒是都去天津了，看他们晚上还在看电影，可恶???，就应该让床单好好教育教育???
同时也回顾了下初中组给ljh P的图，佳和学长好帅，拜谢佳和，所以佳和什么时候请sbf吃饭啊/yiw
另附：最优解第一页（大嘘）
P4495
首先我们能发现，最终背包内装到体积 \(v\) 可以这么表示：
我们可以发现这个形式很像裴蜀定理，我们就可以得出结论：当 \(v\) 能被表示出来时，选取的物品一定满足 \(\gcd(a_1, a_2, \cdots a_k, p) | v\)。同时又因为 \(\gcd(a_1, a_2, \cdots a_k, p) | p\)，因此 \(\gcd(a_1, a_2, \cdots a_k, p) | \gcd(p, v)\)。这提示着我们可以预处理出 \(p\) 的每个约数的答案，每次询问只需要求 \(\gcd\) 即可。
现在我们的目标就是求出当 \(\gcd(a_1, a_2, \cdots a_k, p)=d\) 时的方案数，我们设 \(f[i][j]\) 为前 \(i\) 个物品，当前的 \(\gcd\) 为 \(p\) 的第 \(j\) 个约数时的方案数，转移依旧看选不选即可转移。最后我们再把答案统计到倍数上（因为最终的答案中是整除），时间复杂度 \(O(\sqrt{p}+n\sigma (p)+q\log p)\)。
反正我不知道这玩意能不能过，然后考虑优化一下，我们可以把所有的物品体积转化为 \(\gcd(a_i, p)\)，这样物品的数量也能被压缩到 \(O(\sigma (p))\) 级别了，转移的时候也只是多乘一个 \(2^{cnt}-1\) 的系数。最终复杂度 \(O(\sqrt{p}+\sigma ^2(p)+q\log p)\)
和恋恋一起吃薯片???