Description

墨墨突然对等式很感兴趣, 他正在研究 \(a_1 \cdot x_1 + a_2 \cdot y_2 + \ldots + a_n \cdot b_n = B\) 存在非负整数解的条件, 他要求你编写一个程序, 给定 \(n, \{a_n\}\) 以及 \(B\) 的取值范围, 求出有多少 \(B\) 可以使等式存在非负整数解.

Input

输入的第一行包含 \(3\) 个正整数, 分别表示 \(n, B_{min}, B_{max}\) 分别表示数列的长度、\(B\) 的下界、\(B\) 的上界. 输入的第二行包含 \(n\) 个整数, 即数列 \(\{a_n\}\) 的值.

Output

输出一个整数, 表示有多少 b 可以使等式存在非负整数解.

Sample Input

2 5 10
3 5

Sample Output

5

Data Range

对于 100% 的数据,\(n \leq 12, 0 \leq a_i \leq 5 \times 10^5, 1 \leq B_{min} \leq B_{max} \leq 10^{12}\).

Explanation

先想一下暴力可以洗洗睡了对不对......

然后看这样一个特性, 将 \(\{a_n\}\) 排一下序对结果毫不影响对不对, 所以为了让序列更好看我们先把这个数组排一下序=w=

然后发现这样一个特点,\(a_{2 \ldots n}\) 多出来的部分在创造解的过程中并没有太大用处, 因为多出来的都可以用若干个 \(a_1\) 来代替. 然后就可以反过来想问题:

如果不能暴力对每一个 \(B\) 求解, 那我们为什么不去统计由这些整数能够创造什么样的值? 所以就从 \(0\) 开始暴力这个组合, 但是这样一来又变成了类似 \(O(B_{max})\) 的东西.

考虑这样一件事情, 多出来的我们并不需要真正算出来, 所以只要求每类组合的最小解就 可以了. 另外, 由于整个方程都可以转化为模 \(a_1\) 意义下的方程, 直接用模 \(a_1\) 的余数作为节点建一个最短路即可.

注意在这里 SPFA 目测会写挂, 所以用堆优化 Dijkstra.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 500100, maxm = 5001000, maxN = 100;
const lli infinit = 0x007f7f7f7f7f7f7fll;

class HeapDijkstra
{
public:
    struct edge
    {
        int u, v;
        lli len;
        edge *next;
    };
    int n, s, ecnt;
    edge *edges[maxn], epool[maxm];
    lli dist[maxn];
    void add_edge(int u, int v, lli len)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v; p->len = len;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    priority_queue< pair<lli, int>,
        vector< pair<lli, int> >,
        greater< pair<lli, int> > > que;
    void eval(void)
    {
        for (int i = 0; i < n; i++)
            dist[i] = infinit;
        dist[s] = 0;
        que.push(make_pair(dist[s], s));
        while (!que.empty()) {
            pair<lli, int> pr = que.top();
            que.pop();
            int p = pr.second;
            if (dist[p] > pr.first)
                continue;
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (dist[p] + ep->len < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->len;
                    que.push(make_pair(dist[ep->v], ep->v));
                }
        }
        return ;
    }
} graph;

int n;
lli minn, maxx;
lli a[maxN];

int main(int argc, char** argv)
{
    scanf("%d%lld%lld", &n, &minn, &maxx);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    // Working this under modulo a[1]
    graph.n = a[1];
    graph.s = 0;
    for (lli i = 0; i < a[1]; i++)
        for (int j = 2; j <= n; j++)
            graph.add_edge(i, (a[j] + i) % a[1], a[j]);
    // Evaluate the modulo group
    graph.eval();
    // Stating under different moduli
    lli res = 0;
    for (lli i = 0; i < a[1]; i++)
        if (graph.dist[i] <= maxx) {
            lli l = max(0ll, (minn - graph.dist[i]) / a[1]),
                r = (maxx - graph.dist[i]) / a[1];
            if (l * a[1] + graph.dist[i] < minn) l += 1;
            if (r * a[1] + graph.dist[i] > maxx) r -= 1;
            res += r - l + 1;
        }
    // Done
    printf("%lld\n", res);
    return 0;
}