BZOJ2118 - Click Here
Description
墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。
Input
输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。
Output
输出一个整数，表示有多少b可以使等式存在非负整数解。
Solutions
询问区间$[L,R]$等价于询问$[1,L-1],[1,R]$。
然后该题其实可以等价看做有$n$个物品$a_i$，询问区间内有多少个可以被凑出来。
假设$p$是$a_i$中的任意一个。
若某个答案$x$是能够被凑出来的，那么$x+k \cdot p,1 \leq k$都能被凑出来，而且容易发现，$x+k \cdot p$对$p$取模的结果都是一样的。
那么，就可以对$p$取模的结果进行分组，只要找到每个组中最小的$x$，那么这个组的所有答案都能由不断加$p$得到。记这个答案为$d_i$，现在的问题是如何求这个$d_i$。
$d_0$是显然为$0$的，因此只需要考虑$d_i,i \in [1,p)$。
对于其他物品$q$，如果$d_i$是已知的，那么可以选择物品$q$，得到转移$d_i+q=d_{(i+q) \, mod \, p}$。不过$q$是有多个的，而$p$是唯一的。因此这个转移其实是一个取最小值的过程，即将这个转移转换成图后，跑最短路得到的结果就是转移后的最终结果。
由于图的节点数是与$p$相关的，因此选最小的$a_i$作为$p$能保证节点数最小。
2017.11.23 Update:
其实，随便拿出一个同余类来分析一下，然后就会发现问题的关键在于求出一个模$p$下的完系，使得完系内的每个数字都是最小的能够被凑出来的数字。
数论太差，现在才知道QAQ。
CODE
CODE - Click Here