【BZOJ 2118】 墨墨的等式

题意

墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。

数据范围

对于100%的数据， N≤12，0≤Ai≤5∗105，1≤BMin≤BMax≤1012。

解题思路： 直接去枚举是不现实的， 我们需要寻求一个更高效的枚举算法。

注意到， 对于 A1 来说， 如果我们得到了一个数 X ， 那么X k×A1， 对于所有 0≤k 都可以得到。

这提示我们， 利用对 A1 取模的同余系进行处理， 假如说， 我们知道了能得到的， 对 A1 取模为 i 的最小正整数Xi， 那么就可以知道 Xi+k×A1 都可以得到， 这样我们利用 O(A1) 的时间， 就可以完成对答案的计算。

现在来看怎么得到 X 序列， 我们可以采用最短路的想法， 将A2A3....AN看成边， 把 0到A1−1 当做点， 来跑最短路就可以了。

复杂度 O(N∗A1∗logN)

代码请自行实现