题解 51nod1984 异或约数和

题解 51nod1984 异或约数和

题面

51nod

首先考虑每个数 $x$ 作为约数贡献的次数,显然是 $\lfloor \frac{n}{x} \rfloor$.

而这样的数只有 $\sqrt{n}$ 个,考虑整除分块.

并且因为异或是会抵消,所以我们只用考虑贡献次数为奇数的块.

现在问题是如何求每个块的异或和.

有一个结论(不会证):$4x \texttt{xor} (4x+1) \texttt{xor} (4x+2) \texttt{xor} (4x+3)=0$

因此 $1\sim k$ 的异或和可以在模 $4$ 的意义下分成 $4$ 类:

  • $k k \bmod 4=0$
  • $1 k \bmod 4=1$
  • $k+1 k \bmod 4=2$
  • $0 k \bmod 4=3$

因此我们就可以 $O(1)$ 地计算区间的异或和,进而解决问题了.

code

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
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <stdio.h>
#include <cstring>
#define ll long long
#define filein(a) freopen(a,"r",stdin)
#define fileout(a) freopen(a,"w",stdout);
using namespace std;

inline ll read(){
ll sum=0,f=1;char c=getchar();
while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}

ll n,ans;

inline ll find(ll x){
int y=x%4;
if(y==0) return x;
else if(y==1) return 1;
else if(y==2) return x+1;
else return 0;
}

int main(){
n=read();
for(ll l=1,r=1;l<=n;l=r+1){
r=n/(n/l);ll sum=n/l;
if(!(sum%2)) continue;
ans^=find(r)^find(l-1);
}
printf("%lld\n",ans);
return 0;
}
感谢您又打赏