Skip to content

11101: 【原1101】SuperXOR

题目

题目描述

author: Jiejun Zhang 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1101

Description

Pangzi recently realized that bitwise XOR operation is just an addition without carries. For example, when computing (1001)_2 XOR (1101)_2, you write down:

  1001
+ 1101
-------
  0100

You see, everything is like an addition, except that there are no carries.

After realizing this, Pangzi invented Super XOR. It is just an addition on decimal numbers without carries. For example, 123 SUPERXOR 789 = 802, since 1+7=8, 2+8=0, 3+9=2.

Now comes a question. Given N, find 1 SUPERXOR 2 SUPERXOR 3 SUPERXOR 4 SUPERXOR ... SUPERXOR N

Input Format

The first line contains an integer T (1 <= T <= 1000), indicating the number of test cases.

T lines follow each containing 1 integers N (1 <= N <= 10^12).

Output Format

Output T lines, each line is an integer: the answer for the corresponding test case.

Sample Input

5
1
2
3
4
120001

Sample Output

1
3
6
0
240001

Case Limits

Time limit: 500 msec

Memory limit: 64 MB

LuminousXLB's solution

// 1101. SuperXOR
// #554592 正确 / 分数100 / 时间80ms / 内存1080kb
#include <iostream>
using namespace std;

int main(int argc, char const* argv[])
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif

    int T;
    cin >> T;

    for (int t = 0; t < T; ++t) {
        unsigned long long num;
        cin >> num;

        unsigned long long threshold = 0;
        unsigned long long tmp = num / 100;
        if (tmp > 0) {
            threshold = (tmp - 1) * 100 + 99;
        } else {
            threshold = 0;
        }

        int cnt[16][10] = { 0 };
        for (unsigned long long k = num; k > threshold; k--) {
            unsigned long long tmp = k;
            for (short i = 0; tmp > 0; tmp /= 10, i++) {
                cnt[i][tmp % 10]++;
            }
        }

        short res[16] = { 0 };
        for (int j = 0; j < 16; j++) {
            for (int i = 0; i < 10; i++) {
                res[j] += i * (cnt[j][i] % 10);
            }
        }

        unsigned long long sum = 0;
        for (short i = 15; i >= 0; i--) {
            sum = sum * 10 + (res[i] % 10);
        }

        cout << sum << endl;
    }
    return 0;
}