[51nod异或约数和] 整除分块+打表找规律
- emm。首先我想到一个\(n*log_2 n\)的算法，就是对于每一个数，枚举它的倍数，然后筛一下。35分get。
- 诶，在计算总答案的公式中，一个数被异或的时候，肯定是被作为约数的时候。那么一个数被异或的次数肯定是\(\frac{n}{i}\)。如果为奇数，就把它异或上，不然就不管。\(O(n)\)算法，45分美滋滋。
- 嗯？\(\frac{n}{i}？\)整除分块搞一下是不是就\(\sqrt n\)了啊。哦，但是它好像涉及到一个求连续区间的异或和问题，我们需要\(O(1)\)。转化一下，\(l到r\)的区间异或和等于\(1\)到\(l-1\)的异或和^\(1\)到\(r\)的异或和。从1到n的异或和怎么\(O(1)\)求？打表找规律！
- 设\(f(n)\)为1到n的异或和，则：
\[if(n~ mod~4=1),~f(n)=1\]
\[if(n~mod~4=2),~f(n)=n+1\]
\[if(n~mod~4=3),~f(n)=0\]
\[if(n~mod~4=0),~f(n)=n\] - 盗一下某人的证明：
证明：
我们先来考虑\(f(2^k,2^{k+1}-1)\)
从\(2^k\)到\(2^{k+1}-1\)这\(2^k\)个数，最高位的一个数为\(2^k\)；
若有\(k>=1\),则\(2^k\)为偶数，将这\(2^k\)个数的最高位去掉，异或和不变
因此\(f(2^k,2^{k+1}-1)=f(2^k-2^k,2^{k+1}-2^k-1)=f(0,2^{k}-1)\)
因而存在\(f(0,2^{k+1}-1)=f(0,2^k-1) xor f(2^k,2^{k+1}-1)=0\)
即\(f(0,2^k-1)=0\)
对于\(，f(0,n)，n\geq4\)设n二进制表示的最高位1在第k位k>=2;
\(f(0,n)=f(0,2^k-1) xor f(2^k,n)=f(2^k,n)\)
对于\(2^k\)到\(n\)这\(n-2^k+1\)个数，最高位共有\(m=n-2^k+1\)个1，去除最高位的1
当n为奇数时，m为偶数此时有\(f(0,n)=f(2^k,n)=f(0,n-2^k)|2^k\)
由于\(n-2^k\)与n奇偶性相同，递推上面的公式可得\(f(0,n)=f(0,n-2^k-2^{k-1}-2^{k-2}\cdots -2^2)=f(0,n\%4)\)
当\(n\%4=1\)时\(f(0,n)=f(0,1)=1\)
当\(n\%4=3\)时\(f(0,n)=f(0,3)=0\)
当n为偶数时，m为奇数，因而\(f(0,n)=f(2^k,n)=f(0,n-2^k)xor2^k\)
也相当于最高位不变，递推公式可得
\(f(0,n)=f(0,n\%4)xor 2^kxor\) \(n[k]*2^k-1 xor\cdots\) \(n[2]*2^2\)
n[k]表示n的二进制表示的第k位
显然当n为偶数时 \(f(0,n)\)的二进制从最高位到第3位和n的二进制表示相同
此时我们只需要判断第二位
当\(n\%4=0\)时\(f(0,n)=n\)
当\(n\%4=2\)时\(f(0,n)=n+1\)
综上所述：
\[f(0,n)=f(1,n)\begin{cases}
n\ \ \ \ \ \ \ \quad n\%4=0\\
1\ \ \ \ \ \ \ \quad n\%4=1\\n+1 \quad n\%4=2\\0\ \ \ \ \ \ \ \quad n\%4=3\\
\end{cases}\]