「題解」Codeforces 1559E Mocha and Stars

莫比烏斯反演的另外一種形式：

如果有：

\[f(n)=\sum_{n|d}g(d)

\]

則有：

\[g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)

這裡的 \(d\) 通常是小于等于一個界限，也就是題目中所給定的 "\(n\)"。

特别地，當 \(n=1\) 時，\(g(1)=\sum \mu(d)f(d)\)，也可以了解為容斥系數為 \(\mu\) 的容斥。

對第三個條件進行莫比烏斯反演，得：

\[ans=\sum_{d=1}^m \mu(d)f(d)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#define int long long
#define mp std::make_pair
typedef long long ll;
const ll mod = 998244353;
void cAdd(ll &x, ll y) { x = (x + y >= mod) ? (x + y - mod) : (x + y); }
ll Add(ll x, ll y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
ll Mod(ll x) { return (x+mod)%mod; }
typedef std::pair<int, int> pii; 
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T>
T& read(T& r) {
	r = 0; bool w = 0; char ch = getchar();
	while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
	while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
	return r = w ? -r : r;
}
const int N = 500010;
int n, m, L[N], R[N], l[N], r[N];
int ct, prime[N], mu[N];
bool vis[N];
void pre() {
	vis[1] = 1; mu[1] = 1;
	for(int i = 2; i <= 500000; ++i) {
		if(!vis[i]) {
			prime[++ct] = i;
			mu[i] = -1;
		}
		for(int j = 1; j <= ct && i * prime[j] <= 500000; ++j) {
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) mu[i * prime[j]] = 0;
			else mu[i * prime[j]] = mu[i] * mu[prime[j]];
			if(i % prime[j] == 0) break;
		}
	}
}
ll f[N], g[N], ans;
signed main() {
	pre();
	read(n); read(m);
	for(int i = 1; i <= n; ++i) read(L[i]), read(R[i]);
	for(int d = 1; d <= m; ++d) {
		if(!mu[d]) continue ;
		for(int i = 1; i <= n; ++i) l[i] = (L[i]+d-1)/d, r[i] = R[i]/d;
		int s = m/d;
		for(int i = 0; i <= s; ++i) g[i] = 1;
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= s; ++j) f[j] = 0;
			for(int j = l[i]; j <= s; ++j)
				f[j] = Add(g[j-l[i]], (j>=r[i]+1)?Mod(-g[j-r[i]-1]):0);
			g[0] = 0;
			for(int j = 1; j <= s; ++j)	g[j] = Add(g[j-1], f[j]);
		}
		ans = Add(ans, Mod(mu[d] * g[s] % mod));
	}
	printf("%lld\n", ans);
	return 0;
}