Description

给定 \(\{x_n\}\)，\(y\) 为任意实数，求出在 \([l,r]\) 内 \(\displaystyle\sum_{i=1}^{n}\lfloor\dfrac{y}{x_i}\rfloor\) 有多少种取值。

link：https://www.luogu.com.cn/problem/P9489

Solution

• 可以表示出的取值一定能被为某个 \(x_i\) 的倍数的 \(y\) 表示出。
• 根据上面的结论，一个能被表示出的值有一个唯一对应的为某个 \(x_i\) 倍数的 \(y\)。
• 故统计 \(y\) 的个数即可。二分出最大的合法取值，然后容斥。
• 时间复杂度 \(\mathcal{O}(2^n+\log l)\)。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
namespace Milkcat {
	typedef __int128 LL;
	typedef pair<LL, LL> pii;
	const int N = 1e6 + 5;
	int n, l, r, a[N];
	LL lcm(LL x, LL y) { return x * y / __gcd(x, y); }
	LL dfs(LL dep, LL sum, LL lmt, LL cof) {
		if (sum > lmt) return 0;
		if (dep > n) return (sum > 1) * lmt / sum * cof;
		return dfs(dep + 1, sum, lmt, cof) + dfs(dep + 1, lcm(sum, a[dep]), lmt, -cof);
	}
	LL solve(int m) {
		LL l = 1, r = 1e18;
		while (l <= r) {
			LL mid = (l + r) >> 1, qwq = 0;
			for (int i = 1; i <= n; i ++) qwq += mid / a[i];
			if (qwq <= m) l = mid + 1;
			else r = mid - 1;
		}
		return dfs(1, 1, r, -1);
	}
	int main() {
		cin >> n >> l >> r;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		cout << (long long)(solve(r) - solve(l - 1)) << '\n';
		return 0;
	}
}
int main() {
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}