我们设最小的系数为\(m\)。

那么如果\(B=im+j\)(\(i,j\)为非负整数,\(j<m\))有整数解,那么\(B=(i+k)m+j\)(\(k\)为正整数)也有整数解。我们只需要把\(B=im+j\)的整数解中系数\(m\)对应的未知数加\(k\)就好了。

所以我们记\(d_i\)表示\(B\)在\(mod\ m\)意义下同余\(i\),并且这个\(B\)有解的最小的\(B\)。

显然\(d_0=0\)。

以及我们可以用\(d_i+a_j\)更新\(d_{(i+a_j)mod\ m}\)。

那么可以理解为对于任意\(0\le i<m\)和\(1\le j\le n\),节点\(i\)到节点\((i+a_j)mod\ m\)有一条权值为\(a_j\)的单向边。那么\(d_i\)就是节点0到节点\(i\)的最短路。

所以我们之所以选择最小的系数作为\(m\),是为了减少状态数。

跑一遍玄学的SPFA就能够处理出\(d\)了。

那么在\(mod\ m\)意义下和\(i\)同余且小于等于\(x\)的合法的\(B\)的取值数量为\(\lfloor\frac{x-d_i+m}{m}\rfloor\)。

于是我们设\(0\le B\le x\)时,使得方程有非负整数解的\(B\)取值的数量为\(ans(x)\),则\(ans(x)=\sum_{i=0}^{m-1}\lfloor\frac{max(x-d_i+m,0)}{m}\rfloor\)

题目所求即为\(ans(BMax)-ans(BMin-1)\)。

code:

#include
    
     using namespace std;const long long INF=1e13;struct edge{    int t,v,nxt;}e[6000010];int n,a[15],mn=1e9,cnt,be[500010],t,vis[500010];long long bl,br,dis[500010],tot;queue
     
      q;void add(int x,int y,int val){    e[++cnt].t=y,e[cnt].v=val,e[cnt].nxt=be[x],be[x]=cnt;}void SPFA(){    for(int i=1;i
      
       dis[t]+e[i].v?dis[e[i].t]=dis[t]+e[i].v,(!vis[e[i].t]?q.push(e[i].t),vis[e[i].t]=1:0):0;    }}long long ANS(long long x){    tot=0;    for(int i=0;i