E. Red-Black Pepper（数论/扩展欧几里得）

题目 参考

题意

给定n道菜，每道菜有两种烹饪方式（对应a类调料料和b类调料），美味度分别为ai和bi。

给定m个查询，给定x和y，只允许购买x的整数倍a类调料和，y的整数倍的b类调料。 问能否刚好购买这些调料，使得x * x0 + y * y0 == n，且使得n道菜的美味度最大化。 如果不能刚好购买，输出-1；如果能刚好购买，输出最大的美味度。

思路

扩展欧几里得，求出所有解集，然后在所有解集里边，找出离最佳答案最佳的2组。

最佳答案可以通过预处理计算得出。 详见代码。

官方代码

#include 
#define forn(i, n) for (int i = 0; i