CF1559 - E. Mocha and Stars

E. Mocha and Stars

题意

给出 $n$ 个区间 $[l_i, r_i]$ 和 $m$，保证 $l_i\leqslant r_i\leqslant m$，求：

$$\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}\cdots\sum_{a_n=l_n}^{r_n}[\text{gcd}(a_1,a_2,\ldots,a_n)=1]\cdot[a_1+a_2+\cdots+a_n\leqslant m]$$

思路

可以使用Mobius反演转换 $[\text{gcd}(a_1,a_2,\cdots,a_n)=1]$，$[a_1+a_2+\cdots+a_n\leqslant m]$ 可以使用01背包解决（前缀和优化）。

下面推下式子：

$$\begin{aligned} &\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}\cdots\sum_{a_n=l_n}^{r_n}[\text{gcd}(a_1,a_2,\ldots,a_n)=1]\cdot[a_1+a_2+\cdots+a_n\leqslant m]\\ =&\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}\cdots\sum_{a_n=l_n}^{r_n}\sum_{d|\text{gcd}(a_1,\ldots,a_n)}\mu(d)\cdot[a_1+a_2+\cdots+a_n\leqslant m]\\ =&\sum_{d=1}^{\min(r_1,r_2,\ldots,r_n)}\mu(d)\sum_{a_1=\left\lceil\frac{l_1}{d}\right\rceil}^{\left\lfloor\frac{r_1}{d}\right\rfloor}\cdots\sum_{a_n=\left\lceil\frac{l_n}{d}\right\rceil}^{\left\lfloor\frac{r_n}{d}\right\rfloor}[a_1d+a_2d+\cdots+a_nd\leqslant m]\\ =&\sum_{d=1}^{\min(r_1,r_2,\ldots,r_n)}\mu(d)\sum_{a_1=\left\lceil\frac{l_1}{d}\right\rceil}^{\left\lfloor\frac{r_1}{d}\right\rfloor}\cdots\sum_{a_n=\left\lceil\frac{l_n}{d}\right\rceil}^{\left\lfloor\frac{r_n}{d}\right\rfloor}[a_1+a_2+\cdots+a_n\leqslant \left\lfloor\frac{m}{d}\right\rfloor]\\ \end{aligned}$$

考虑计算 $\displaystyle \sum_{a_1=\left\lceil\frac{l_1}{d}\right\rceil}^{\left\lfloor\frac{r_1}{d}\right\rfloor}\cdots\sum_{a_n=\left\lceil\frac{l_n}{d}\right\rceil}^{\left\lfloor\frac{r_n}{d}\right\rfloor}[a_1+a_2+\cdots+a_n\leqslant \left\lfloor\frac{m}{d}\right\rfloor]$ 的复杂度。

这个式子可以通过01背包dp完成计算，设 $f(i, j)$ 表示前i个物品，总重量和为j的方案数，转移为：

$$f(i,j)=\sum_{k=l_i}^{r_i}f(i-1,j-k)$$

用前缀和优化后，dp总复杂度为 $O(N\left\lfloor\frac{M}{d}\right\rfloor)$

则计算 $\displaystyle \sum_{d=1}^{\min(r_1,r_2,\ldots,r_n)}\mu(d)\sum_{a_1=\left\lceil\frac{l_1}{d}\right\rceil}^{\left\lfloor\frac{r_1}{d}\right\rfloor}\cdots\sum_{a_n=\left\lceil\frac{l_n}{d}\right\rceil}^{\left\lfloor\frac{r_n}{d}\right\rfloor}[a_1+a_2+\cdots+a_n\leqslant \left\lfloor\frac{m}{d}\right\rfloor]$

直接枚举的总复杂度为 $O(\sum_{i=1}^MN\left\lfloor\frac{M}{d}\right\rfloor)=O(NMlogM)$。

如果使用数论分块的总复杂度为 $O(N\sqrt Mlog\sqrt M)$，但其实常数很大。

直接暴力枚举d：

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 50 + 10;
const int M = 1e5 + 10;
int mu[M];
bool vis[M];
vi prim;
void Euler(int n) {
	mu[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			prim.pb(i);
			mu[i] = -1;
		}
		for (auto j : prim) {
			int t = i * j;
			if (t > n) break;
			vis[t] = 1;
			if (i % j == 0) {
				mu[t] = 0;
				break;
			}
			mu[t] = -mu[i];
		}
	}
}
int n, m;
int L[N], R[N];
int dp[M], sum[M];
int calc(int d) {
	int mx = m / d;
	for (int i = 0; i <= mx; i++) sum[i] = dp[i] = 0;
	for (int i = 0; i < n; i++) {
		int l = (L[i]+d-1)/d, r = R[i]/d;
		for (int j = 1; j <= mx; j++) {
			if (i == 0 && j >= l && j <= r) dp[j] = 1;
			else if (i != 0) dp[j] = (j < l) ? 0 : (sum[j-l] - sum[max(0ll, j-r-1)] + P) % P;
		}
		for (int j = 1; j <= mx; j++) {
			sum[j] = (sum[j-1] + dp[j]) % P;
		}
	}
	return sum[mx];
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	Euler(m);
	int mn = 1e9;
	for (int i = 0; i < n; i++) {
		cin >> L[i] >> R[i];
		mn = min(mn, R[i]);
	}
	int ans = 0;
	for (int i = 1; i <= mn; i++) {
		ans = (ans + mu[i] * calc(i) + P) % P;
	}
	cout << ans << '\n';
	return 0;
}

使用数论分块：

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 50 + 10;
const int M = 1e5 + 10;
int mu[M], smu[M];
bool vis[M];
vi prim;
void Euler(int n) {
	mu[1] = smu[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			prim.pb(i);
			mu[i] = -1;
		}
		for (auto j : prim) {
			int t = i * j;
			if (t > n) break;
			vis[t] = 1;
			if (i % j == 0) {
				mu[t] = 0;
				break;
			}
			mu[t] = -mu[i];
		}
		smu[i] = smu[i-1] + mu[i];
	}
}
int n, m;
int L[N], R[N];
int dp[M], sum[M];
int calc(int d) {
	int mx = m / d;
	for (int i = 0; i <= mx; i++) sum[i] = dp[i] = 0;
	for (int i = 0; i < n; i++) {
		int l = (L[i]+d-1)/d, r = R[i]/d;
		for (int j = 1; j <= mx; j++) {
			if (i == 0 && j >= l && j <= r) dp[j] = 1;
			else if (i != 0) dp[j] = (j < l) ? 0 : (sum[j-l] - sum[max(0ll, j-r-1)] + P) % P;
		}
		for (int j = 1; j <= mx; j++) {
			sum[j] = (sum[j-1] + dp[j]) % P;
		}
	}
	return sum[mx];
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	Euler(m);
	int mn = 1e9;
	for (int i = 0; i < n; i++) {
		cin >> L[i] >> R[i];
		mn = min(mn, R[i]);
	}
	int ans = 0;
	for (int l = 1, r; l <= mn; l = r + 1) {
		r = m / (m / l);
		for (int i = 0; i < n; i++) {
			r = min(r, R[i]/(R[i]/l));
			if (L[i]-1 >= l) r = min(r, (L[i]-1)/((L[i]-1)/l));
		}
		ans = (ans + (smu[r] - smu[l-1] + P) % P * calc(l) % P + P) % P;
	}
	cout << ans << '\n';
	return 0;
}