题目描述

给定 $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$ 的情况了，于是就可以直接类欧一下就行了

板子如下：

#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