B 异或约数和

https://www.51nod.com/Contest/Problem.html#!#contestProblemId=780 

 思路：

先看一个问题：f(n)表示n的约数个数，现在给出n，要求求出f(1)到f(n)的总和。 

可以发现[1,n]中约数有i的个数是n/i ，然后进行分块处理，在这里我们举个例子，比如n为100时，100/34=2，100/2=50，所以小于n的数约数中有34到50其中一个的数有2个，所以直接ans+=2*(50-34+1)。

for(int i=1,j;i<=n;i=j+1){
    j=n/(n/i);
    ans+=(n/i)*(j-i+1);
}

看另一个问题：求1-n的异或和。

在这个博客里写了

再回来看这道题，求他们约数的异或和再将约数的异或和再异或：

可以看出，若约数的个数n/i是偶数时，约数异或和为0，不做考虑，当约数个数为奇数时，可以从i异或到j

#include<bits/stdc++.h>
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define ll long long
#define ld long double
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lcm(a,b) ((a)*(b)/(__gcd((a),(b))))
#define mod 1000000007
using namespace std;
const int N = 1e3 + 10;
ll n, ans;
ll xor_n(ll n) {
    ll ans = 0;
    if(!(n & 1))
        n++, ans = n;
    ll num = (n + 1ll) / 2ll;
    if(num & 1)
        ans ^= 1;
    return ans;
}
int main() {
    cin >> n;
    for(ll i = 1, j; i <= n; i = j + 1) {
        j = n / (n / i);
        if((n / i) & 1) {
            ans ^= xor_n(j)^xor_n(i - 1);
        }
    }
    cout << ans;
    return 0;
}