题目描述

给定 $n(1 \le n \le 10^{12})$,求:

$$
\oplus_{i=1}^{n} (n \bmod i)
$$

其中 $\oplus$ 表示异或,即二进制下不进位加法

题解

稍微化简一下:

$$
\begin{aligned}
&\oplus_{i=1}^{n}(n \bmod i) \\
=&\oplus_{i=1}^{n}n - \left\lfloor \frac{n}{i} \right\rfloor i \\
=&\sum_{\omega=0}^{60} 2^{\omega} \left(\left( \sum_{k} \sum_{i=1}^{n} \left\lfloor \frac{n - ki}{2^{\omega}} \right\rfloor [k=\left\lfloor \frac{n}{i} \right\rfloor] \right) \bmod 2 \right)
\end{aligned}
$$

考虑到可以对 $k=\left\lfloor \frac{n}{i} \right\rfloor$ 进行数论分块,那么就只需要解决:

$$
\sum_{x=0}^{n-1} \left\lfloor \frac{ax+b}{c} \right\rfloor
$$

然而类欧只能直接做 $a,b,c > 0$ 的情况,在本题中 $a<0$,需要稍微转换一下

为了方便以后的做题,不妨都考虑一遍

如果 $c<0$,可以在分式上下都乘以 $-1$,仍然等价,于是只需要考虑 $c>0$ 的情况

如果 $a<0$,则:

$$
\begin{aligned}
&\sum_{x=0}^{n-1} \left\lfloor \frac{ax+b}{c} \right\rfloor \\
=&\sum_{x=0}^{n-1} \left\lfloor \frac{(-a)(x-(n-1))+b}{c} \right\rfloor \\
=&\sum_{x=0}^{n-1} \left\lfloor \frac{(-a)x+b+a(n-1)}{c} \right\rfloor \\
\end{aligned}
$$

于是就转化成了 $a,c>0$ 的情况

如果 $b<0$,则:

$$
\begin{aligned}
&\sum_{x=0}^{n-1} \left\lfloor \frac{ax+b}{c} \right\rfloor \\
=&\left(\sum_{x=0}^{n-1} \left\lfloor \frac{ax+b+kc}{c} \right\rfloor \right)-kn \\
\end{aligned}
$$

需要保证 $b+kc \ge 0$,即 $k=\left\lceil \frac{-b}{c} \right\rceil$

此时就是 $a,b,c>0$ 的情况了,于是就可以直接类欧一下就行了

板子如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define ll __int128
inline ll sub_f(ll a, ll b, ll c, ll n) {
if(n <= 0) return 0;
return
n * (n - 1) / 2 * (a / c)
+ n * (b / c)
+ sub_f(c, (a * n + b) % c, a % c, (a % c * n + b % c) / c);
}
inline ll f(ll a, ll b, ll c, ll n) {
if(c < 0) {
c = -c;
a = -a, b = -b;
return f(a, b, c, n);
}
if(a < 0) {
a = -a;
return f(a, b - a * (n - 1), c, n);
}
if(b < 0) {
b = -b;
ll k = b / c + (b % c != 0);
return f(a, k * c - b, c, n) - k * n;
}
return sub_f(a, b, c, n);
}
#undef ll