『取模与异或 类欧几里得算法』

<更新提示>

<第一次更新>

<正文>

取模与异或

Description

求 ((n mod 1)oplus (n mod 2)oplus cdots oplus (n mod n))。

(nleq 10^{11})。

Input Format

一行，一个正整数n。

Output Format

一行，一个正整数表示答案

Sample Input

5

Sample Output

2

解析

很容易想到『约数之和 整除分块』这道题。

但是好像还不能直接整除分块做，应该我们不能快速求等差数列异或和之类的东西。于是考虑到异或是不进位加法，那就拆位试试看。

也就是把式子转换成这个样子：

[bigoplus_{i=1}^nn mod i=sum_{k}sum_{i=1}^nleft(left lfloor frac{n mod i}{2^k} right rfloor mod 2right)times 2^k]

于是就可以推式子了

[sum_{k}sum_{i=1}^nleft(left lfloor frac{n mod i}{2^k} right rfloor mod 2right)times 2^k =sum_{i=1}^nsum_{k}left(left lfloor frac{n mod i}{2^k} right rfloor mod 2right)times 2^k =sum_{i=1}^nsum_{k}left(left lfloor frac{n-lfloorfrac{n}{i}rfloortimes i }{2^k} right rfloor mod 2right)times 2^k]

(k)代表二进制中的每一位，是不是有点像类欧几里得算法求的那个式子，这引导我们继续推导下去。

首先，枚举(k)是(log_2n)级别的复杂度，我们能够承受，但是枚举(n)的复杂度是承受不了的，我们需要整除分块一下才能把枚举(n)的复杂度降下来。

那么我们分块枚举(n)，并枚举每一个(k)，剩下的就是要快速求这个式子：

[sum_{i=l}^{r}left lfloor frac{n-lfloorfrac{n}{i}rfloortimes i }{2^k} right rfloor]

由于(k,lfloor frac{n}{i} rfloor)已经枚举了，我们就把有关量给换成常数(a,c)。

[sum_{i=l}^{r}left lfloor frac{n-lfloorfrac{n}{i}rfloortimes i }{2^k} right rfloor=sum_{i=l}^rleftlfloor frac{n-atimes i}{c} rightrfloor]

已经很像类欧几里得的式子了，但仍然不能快速求，还要再处理一下下标，化简一下：

[sum_{i=l}^rleftlfloor frac{n-atimes i}{c} rightrfloor=sum_{i=0}^{r-l}leftlfloor frac{n-atimes (i+l)}{c} rightrfloor]

当(iin[0,r-l])时，((i+l))和((r-i))取到的值域是一样的，那么我们就换一下：
[sum_{i=0}^{r-l}leftlfloor frac{n-atimes (i+l)}{c} rightrfloor=sum_{i=0}^{r-l}leftlfloor frac{n-atimes (r-i)}{c} rightrfloor=sum_{i=0}^{r-l}leftlfloor frac{n-atimes r+atimes i}{c} rightrfloor=sum_{i=0}^{r-l}leftlfloor frac{atimes i+n-atimes r}{c} rightrfloor]

还记得(a=lfloor frac{n}{i} rfloor)吗？把它带回去。

[sum_{i=0}^{r-l}leftlfloor frac{atimes i+n-atimes r}{c} rightrfloor=sum_{i=0}^{r-l}leftlfloor frac{atimes i+n-lfloor frac{n}{i} rfloortimes r}{c} rightrfloor=sum_{i=0}^{r-l}leftlfloor frac{atimes i+n mod r}{c} rightrfloor]

设[f(a,b,c,n)=sum_{i=0}^nleftlfloorfrac{atimes i+b}{c}rightrfloor]

那么[sum_{i=0}^{r-l}leftlfloor frac{atimes i+n mod r}{c} rightrfloor=f(a,n mod r,r-l)=f(leftlfloor frac{n}{i}right rfloor,2^k,r-l)]

枚举(l,r,k)，直接用类欧几里得算法计算即可。

这样做时间复杂度是(O(sqrt nlog^2n))的，可以直接暴力计算前(3times 10^7)个值，减小常数。

(Code:)

#include <bits/stdc++.h>
using namespace std;
inline bool f(long long a,long long b,long long c,long long n)
{
    if ( a == 0 ) return ( ( n + 1 ) & ( b / c ) & 1 ) > 0;
    if ( a >= c || b >= c )
    {
        long long val = ( n & 1 ) ? ( n + 1 ) / 2 * n : n / 2 * ( n + 1 );
        return ( ( f( a % c,b % c,n ) + ( a / c ) * val + ( n + 1 ) * ( b / c ) ) & 1 ) > 0;
    }
    else
    {
        long long val = ( a * n + b ) / c;
        return ( ( ( val * n ) ^ f( c,c - b - 1,a,val - 1 ) ) & 1 ) > 0;
    }
}
int main(void)
{
    freopen("mod.in","r",stdin);
    freopen("mod.out","w",stdout);
    long long ans = 0,n;
    scanf("%lld",&n);
    long long T = min( n,30000000LL );
    for (int i=1;i<=T;i++)
        ans ^= n % i;
    for (long long l=T+1,r;l<=n;l=r+1)
    {
        r = n/l ? min( n/(n/l),n ) : n;
        long long lim = n/l * (r-l) + n%r,val = 0;
        for (long long k=1;k<=lim;k<<=1)
            val += f( n/l,n%r,k,r-l ) * k;
        ans ^= val;
    }
    printf("%lldn",ans);
    return 0;
}