埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 F 1 + 2 = 3?(找规律)

Description:

小Y在研究数字的时候，发现了一个神奇的等式方程 $x⨁2x=3x$x⨁2x=3x，他屈指算了一下有很多正整数x满足这个等式，比如1和2，现在问题来了，他想知道从小到大第N个满足这个等式的正整数，请你用程序帮他计算一下。
( $⨁$⨁ 表示按位异或运算)

Input:

第一行是一个正整数 $T(T\le 100)$T(T≤100)，表示查询次数。

接着有T行，每行有一个正整数 $N(N\le 10^{12})$N(N≤1012)，表示小Y的查询。

Output:

对于每一个查询N，输出第N个满足题中等式的正整数，并换行。

Sample Input:

4
1
2
3
10

Sample Output:

1
2
4
18

题目链接

题目要求查询符合要求的第n个数是多少，由于最大查询到第10¹²个数，所以肯定不能直接暴力打表，这就需要通过不完全归纳法找规律了，先写个程序暴力跑一遍符合要求的数，输出出来找规律。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 100;
const double eps = 1e-5;
const double e = 2.718281828459;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 1; i < maxn; ++i) {
        if ((i ^ (2 * i)) == (3 * i)) {
            cout << i << endl;
        }
    }
    return 0;
}

输出结果:

1
2
4
5
8
9
10
16
17
18
20
21
32
33
34
36
37
40
41
42
64
65
66
68
69
72
73
74
80
81
82
84
85

以上输出结果我找不到什么规律，但是题目要求是有按位进行异或运算的操作，把上面程序结果转换为二进制输出出来再来找规律。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 502;
const double eps = 1e-5;
const double e = 2.718281828459;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 1; i < maxn; ++i) {
        if ((i ^ (2 * i)) == (3 * i)) {
            cout << bitset<sizeof(i) * 2>(i) << endl;
        }
    }
    return 0;
}

输出结果:

00000001
00000010
00000100
00000101
00001000
00001001
00001010
00010000
00010001
00010010
00010100
00010101
00100000
00100001
00100010
00100100
00100101
00101000
00101001
00101010
01000000
01000001
01000010
01000100
01000101
01001000
01001001
01001010
01010000
01010001
01010010
01010100
01010101

这里规律就很明显了:

以数字位数划分，数字个数为一个斐波那契数列。
代码实现先根据输入的查询位置和斐波那契数列前n项和的关系判断结果位数，二进制中最高位一定是1，所以先把结果从0加上2的位数次方，然后n减去2的位数次方后，二进制中第二个1的位置还是用n循环查询，直到n为0。注意每个位数长度第一个数是2的位数次方，后面全为0。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 502;
const double eps = 1e-5;
const double e = 2.718281828459;
 
ll Fib[60];
ll Fib_sum[60];
 
void init() {
    Fib[1] = 1;
    Fib_sum[1] = 1;
    Fib[2] = 1;
    Fib_sum[2] = 2;
    for (int i = 3; i < 60; ++i) {
        Fib[i] = Fib[i - 1] + Fib[i - 2];
        Fib_sum[i] = Fib[i];
        Fib_sum[i] += Fib_sum[i - 1];
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    int t;
    cin >> t;
    while (t--) {
        ll n, ans = 0;
        cin >> n;
        bool flag = 0;
        while (n) {
            if (flag) {
                if (n == 1) {
                    break;
                }
                else {
                    n--;
                }
            }
            ll add = 1;
            int book = 1;
            for (int i = 1; i < 60; ++i) {
                if (Fib_sum[i] >= n) {
                    book = i;
                    break;
                }
            }
            if (book > 2) {
                n -= Fib_sum[book - 1];
            }
            else {
                n -= Fib_sum[book];
            }
            for (int i = 1; i < book; ++i) {
                add *= 2;
            }
            ans += add;
            flag = 1;
        }
        cout << ans << endl;
    }
    return 0;
}