【loj 6344】异或和

题目描述

给定 $n(1\le n\le {10}^{12})$，求：

$${\oplus }_{i=1}^n(nmodi)$$

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

题解

稍微化简一下：

$$\begin{array}{rl}& {\oplus }_{i=1}^n(nmodi)\\ =& {\oplus }_{i=1}^{n}n-\lfloor \frac{n}{i}\rfloor i\\ =& \sum _{\omega =0}^{60}{2}^{\omega }((\sum _k\sum _{i=1}^n\lfloor \frac{n-ki}{2^{\omega }}\rfloor [k=\lfloor \frac{n}{i}\rfloor ])mod2)\end{array}$$

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

$$\sum _{x=0}^{n-1}\lfloor \frac{ax+b}{c}\rfloor$$

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

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

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

如果 $a<0$，则：

$$\begin{array}{rl}& \sum _{x=0}^{n-1}\lfloor \frac{ax+b}{c}\rfloor \\ =& \sum _{x=0}^{n-1}\lfloor \frac{(-a)(x-(n-1))+b}{c}\rfloor \\ =& \sum _{x=0}^{n-1}\lfloor \frac{(-a)x+b+a(n-1)}{c}\rfloor \end{array}$$

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

如果 $b<0$，则：

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

需要保证 $b+kc\ge 0$，即 $k=\lceil \frac{-b}{c}\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