自动搬运

查看原文

来自洛谷，原作者为

	Treeloveswater **

搬运于2025-08-24 21:53:58，当前版本为作者最后更新于2018-04-15 09:23:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

乱逛的时候看到了这题
随手推了一下，就A了。
为啥要结论？我来说一种非常严谨的做法。 并且是O(1)的。
题目要求 1^2^...^n，我们强制使得n为奇数 ，就是说如果n是偶数，我们就让n=n+1,然后让答案最后再异或n即可。
我们现在考虑一个奇数A，它的二进制形式是：ABCD1
A-1一定是偶数，其形式一定是 ABCD0
也就是说 A^(A-1)=000001 所以我们发现，除了最右边那一位，其他位都是0！
也就是说，我们现在只需要统计有多少个奇数即可！ 那么就很简单了。代码如下。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
int main(){
  ll ans=0;
  scanf("%lld",&n);
  if(!(n&1)) n++,ans=n;
  ll num=(n+1ll)/2ll;
  if(num&1) ans^=1;
  cout<<ans;
}