# 14319: 【原4319】异或和取模

### 题目描述

author: smallling 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4319

## Description

$\oplus$表示异或运算

## Sample Input

10


## Sample Output

9


## ligongzzz's solution

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
int n;
cin >> n;

vector<int> xval(n + 1, 0);
for (int i = 1; i <= n; ++i)
xval[i] = xval[i - 1] ^ i;

int ans = 0;
for (int i = 1; i <= n; ++i) {
int k = n / i, r = n % i;
if (k % 2)
ans ^= xval[i - 1];
ans ^= xval[r];
}

cout << ans;

return 0;
}


## satgo1546's solution

#include <stdio.h>

int t[1000004];
int main() {
int n, i, a = 0;
t[0] = 0;
// 预先计算1 ⊕ 2 ⊕ … ⊕ i。
for (i = 1; i <= 1000000; i++) {
t[i] = t[i - 1] ^ i;
}
scanf("%d", &n);
for (i = 2; i <= n; i++) {
a ^= t[n % i];
if ((n / i) & 1) a ^= t[i - 1];
}
printf("%d\n", a);
return 0;
}


## zqy2018's solution

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
using namespace std;
int f = 1, x = 0;
char c = getchar();
while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, sm[1000005] = {0};
void init(){
REP(i, 1, n)
sm[i] = sm[i - 1] ^ i;
}
void solve(){
int ans = 0;
for (int i = 1; i <= n; ++i){
int p = n / i, t = n % i;
if (p & 1) ans ^= sm[i - 1];
ans ^= sm[t];
}
printf("%d\n", ans);
}
int main(){
init();
solve();
return 0;
}