Skip to content

14319: 【原4319】异或和取模

题目

题目描述

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

Description

给一个正整数$n$,设$x_i = (i\mod 1) \oplus (i \mod 2) \oplus \dots \oplus (i \mod n)$

求$x_1 \oplus x_2 \oplus \dots \oplus x_n$

$\oplus$表示异或运算

Input Format

一行一个数字$n$。 $1 \leq n \leq 10^6$

Output Format

一行一个数字表示答案

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 read(){
    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(){
    n = read();
    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;
}