P2371 / 墨墨的等式

// Code by Heratino & Nelofus
// 彗星になれなかった姿を
// 笑い飛ばしてほしかった

#include <bits/stdc++.h>
using i64 = long long;
using f64 = double;

template<typename Ta, typename Tb>
inline void chkmax(Ta &a, const Tb &b) {if (a < b)  a = b;}
template<typename Ta, typename Tb>
inline void chkmin(Ta &a, const Tb &b) {if (a > b)  a = b;}

constexpr int N = 5e5 + 10;
i64 f[N];
int n;
i64 l, r;

int main() {
    std::cin >> n >> l >> r;
    std::vector<int> a(n);
    for (int &x : a)    std::cin >> x;

    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    int m = a[0];

    for (int i = 1; i < n; i++) {
        for (int k = 0; k < std::__gcd(a[i], m); k++) {
            for (int cur = k, c = 0; c < 2; c += (cur == k)) {
                int nxt = (cur + a[i]) % m;
                chkmin(f[nxt], f[cur] + a[i]);
                cur = nxt;
            }
        }
    }

    i64 ans = 0;
    auto ct = [&](i64 x) {return x >= 0 ? x / m + 1 : 0;};
    for (int i = 0; i < m; i++) {
        ans += ct(r - f[i]) - ct(l - f[i] - 1);
    }
    std::cout << ans << '\n';
    return 0;
}