Skip to content

11201: 【原1201】SuperXOR

题目

题目描述

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

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

q4x3's solution

/**
 * 找规律 + 高精度加法
 * 打表发现99结尾的数加出来都是0
 * 所以直接从上一个99结尾的数开始算
 * 高精度很简单没什么好说的
 * 注意删除前导零
 **/
#include <iostream>

using namespace std;

int T;
long long N, init;
int main() {
    cin >> T;
    for(int i = 0;i < T;++ i) {
        int ans[20] = {0};
        cin >> N;
        init = (N / 100) * 100;
        for(long long i = init;i <= N;++ i) {
            int j = 0;
            long long cur = i;
            while(cur) {
                ans[j] += (cur % 10);
                cur /= 10;
                ans[j] %= 10;
                ++ j;
            }
        }
        int del_0 = 19;
        while(del_0) {
            if(ans[del_0] != 0) break;
            -- del_0;
        }
        for(int i = del_0;i >= 0;-- i)
            cout << ans[i];
        cout << endl;
    }
}

victrid's solution

#include <iostream>
using namespace std;
int dremainder[] = {0, 1, 3, 6, 0, 5, 1, 8, 6, 5};
int main() {
    int total = 0;
    cin >> total;
    long long* ans = new long long[total];
    long long* dig = new long long[total];
    for (int i = 0; i < total; i++) {
        cin >> ans[i];
        long long proc      = ans[i];
        short lowestdigitpo = (proc + 1) % 10;
        //lowest digit self's added + n x {123456789} time (mod===5)
        ans[i] = (dremainder[proc % 10] + (proc / 10 % 2) * 5) % 10;
        proc /= 10;
        //higher digits
        long long zeroph = 1;

        for (int j = 0; proc != 0; j++) {
            zeroph *= 10;
            int procdigit = proc % 10;
            proc /= 10;
            // 123 >4< 5: 4~{0,1,2,3,4,5}
            // lowest digit +1: really effected numbers.
            procdigit = procdigit * lowestdigitpo % 10;
            ans[i] += procdigit * zeroph;
        }
        dig[i] = zeroph / 10;
    }
    for (int i = 0; i < total; i++) {
        if (i)
            cout << endl;
        //! CYKA BLYAT padding zeros
        //errare
        // if (ans[i] == 0) {
        //     cout << '0';
        //     continue;
        // }
        //errare 2
        // while (ans[i] < dig[i]) {
        //     cout << '0';
        //     dig[i] /= 10;
        // }
        cout << ans[i];
    }
    return 0;
}