容斥 C. Strange Function改编题

补题：

题目详情 - 9.段坤爱取模%%% - SUSTOJ

本题或许是参考 Problem - C - Codeforces

根据题意，f(i)就是不能被整除的最小的一个质因子。

打表发现，当15个质因子相乘后，长度就大于18。

因此可以知道小于等于1e16内的正整数x，f(x)一定是前20个质因子之一，且合数一定不行。

前20个质因子：2 3 5 7 11 13 17 19 23 29 31 37 41 43 。在第15个质因子相乘时就大于1e16，因此max(f(i))是小于40的。

现在就是要求：第1个质因子在[l, r]的个数 乘上 第1个质因子，加上 第2个质因子在[l, r]的个数 乘上 第2个质因子个数， … 。需要保证i在[l, r]内仅且一次被计算。考虑容斥。

对于f(i) = k来说，i可以被1 ... k - 1任何一个整除，但是不能被k整除。

f()值为k的个数有：
$$\lfloor \frac{r}{lcm(1,...k-1)}-\frac{r}{lcm(1,...k)}\rfloor -\lfloor \frac{l}{lcm(1,...k-1)}-\frac{l}{lcm(1,...k)}\rfloor$$
如果将[l, r]分成两部分[1, l]和[1, r]来处理的话。

以r为例，f()为k的个数：
$$\lfloor \frac{r}{lcm(1,...k-1)}-\frac{r}{lcm(1,...k)}\rfloor$$
那么，[1, r]内sum就是：
$$\begin{gathered} \sum _{k\ge 2}k\times (\lfloor \frac{r}{lcm(1,...k-1)}-\frac{r}{lcm(1,...k)}\rfloor ) \\ =2\times (r-\lfloor \frac{r}{lcm(1,2)}\rfloor )+3\times (\lfloor \frac{r}{lcm(1,2)}-\frac{r}{lcm(1,2,3)}\rfloor )+... \\ =r+\sum _{k\ge 1}\lfloor \frac{r}{lcm(1,...,k)}\rfloor \end{gathered}$$
同理，可得[1, l]内的sum，两者相减即为答案。对于cf上的C，[1, r]即可。

时间复杂度：前面稠密，后面稀疏，最大为O(41 * 2)。

const int mod = 998244353;
// https://codeforces.com/contest/1542/problem/C
void solve() {
	int l,r; cin>>l>>r;
	int sum = 0;
	int v = 1;
    auto lcm = [&](int a, int b) {
        return a * b / __gcd(a,b);
    };
	for(int i = 1; v <= r; v = lcm(i, v), ++i) {
		sum = (sum + r / v) % mod;
	}
	v = 1;
	for(int i = 1; v <= l - 1; v = lcm(i,v), ++i) {
		sum = (sum - (l - 1) / v + mod) % mod;
	}
	cout<<sum<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

总结

赛时对这题容斥没有找到切入点。这个容斥处理极具有思维性，还是需要多做思维题！

参考：

[Codeforces] number theory (R1600) Part.11 - 知乎 (zhihu.com)

Submission #121200660 - Codeforces