题目描述

ZHY 称一个正整数 $x$ 是可被表示的，当且仅当存在一个实数 $y$，满足：

$$ \left\lfloor \frac{y}{x_1} \right\rfloor + \left\lfloor \frac{y}{x_2} \right\rfloor + \ldots + \left\lfloor \frac{y}{x_n} \right\rfloor = x $$

现在，ZHY 想知道区间 $[l, r]$ 中有多少个正整数是可被表示的。

输入格式

• 第一行输入三个正整数 $n, l, r$。
• 第二行输入 $n$ 个正整数 $x_1, x_2, \ldots, x_n$。

输出格式

• 输出一个整数，表示在区间 $[l, r]$ 中可被表示的正整数的数量。

输入输出样例

输入 #1

2 5 10
2 3

输出 #1

5

说明/提示

样例解释：

• 当 $x = 5$ 时，取 $y = 6$ 成立。
• 当 $x = 6$ 时，取 $y = 8$ 成立。
• 当 $x = 7$ 时，取 $y = 9$ 成立。
• 当 $x = 8$ 时，取 $y = 10$ 成立。
• 当 $x = 10$ 时，取 $y = 12$ 成立。

因此，$5, 6, 7, 8, 10$ 是可被表示的，故答案为 $5$。

数据范围

• 对于 30% 的数据，满足 $l \leq r \leq 10^5$。
• 对于另外 10% 的数据，$n = 1$。
• 对于 100% 的数据，满足以下条件：
• $1 \leq n \leq 25$
• $1 \leq l \leq r \leq 10^9$
• $1 \leq x_1, x_2, \ldots, x_n \leq 10^9$

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

typedef __int128 LL;
int n;
int a[N];

LL gcd(LL a, LL b) {
    return  b ? gcd(b, a % b) : a;
}

bool check(LL x, LL y) {
    LL res = 0;
    for (int i = 1; i <= n; i ++ ) res += y / a[i];

    return res <= x;
}


LL solve(LL x) {
    //先找到满足y / xi <= x的最大ymax
    LL l = 0, r = 1e18;
    while (l < r) {
        LL mid = l + r + 1 >> 1;
        if (check(x, mid)) l = mid;
        else r = mid - 1;
    }

    // 计算 [1, p] 中所有 x 的倍数的个数，使用容斥原理
    LL res = 0, p = l;
    for (int i = 1; i < (1 << n); i ++ ) {
        LL lcm = 1, bits = __builtin_popcount(i);
        for (int j = 1; j <= n; j ++ ) {
            if (!(i & 1 << (j - 1))) continue;
            lcm = lcm * a[j] / gcd(lcm, (LL) a[j]);
            if (lcm > p) break;
        }

        if (bits & 1) res += p / lcm;
        else res -= p / lcm;
    }

    return res;
}

int main() {
    int l, r;
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    LL ansr = solve((LL)r);
    LL ansl = solve((LL)l - 1);

    cout << (long long)(ansr - ansl) << endl;

    return 0;
}