题目链接

https://codeforces.com/problemset/problem/424/C

解题思路

前置知识：
A^0=A
A^A=0
异或具有结合律

直接暴力超时；
第一眼以为整除分块，拉倒吧，整除分块是加法；
打了个表，看列还是有规律的；
所以我当时的想法是统计1 ~ n每个数个数的奇偶，之后再遍历一遍，若是奇数个就异或一下，若是偶数个continue，但是没找到快速统计个数的方法。

正确思路：
还是看列，列的变化是具有周期性的；
我们先统计前缀，什么前缀？sum[i]表示1 ~ i的异或，即1 ^ 2 ^ …… ^ i；
再计算每一列的周期数，如果周期为奇数个，就需要用答案异或一下前缀，若偶数不管；
同时，还不能忘记没到一个周期的部分，我们就算出进行了多少个异或，同样用前缀异或上就行。

大佬讲解

注意：cin，cout超时好像

AC代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int N=1e6+10;

int n;
ll ans,a,sum[N];
int main()
{
//    cin>>n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a),ans^=a,sum[i]=sum[i-1]^i; 

    for(int i=2;i<=n;i++)
    {
        int tmp=(n-n%i)/i;
        if(tmp&1) ans^=sum[i-1];
        ans^=sum[n%i];
    }
    printf("%lld\n",ans);
//    cout<<ans<<endl;
}

打表代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;
int main()
{
    int n,cnt;
    cin>>n;
    for(int i=1;i<=n;i++,cout<<endl)
    for(int j=1;j<=n;j++)
    printf("%2d ",i%j);
}

总结

又是巧用前缀，WTCL，没这意识……