题意

给定数列 $[a_1,a_2,\ldots]$，其递归定义为：$a_1=1$, $a_2=2$, $a_{2n+1}=2a_{2n}$, $a_{2n+2}=a_{2n+1}+r_n$，其中 $n\ge 1$，$r_n$ 是最小的不能表示为 $a_1,a_2,\ldots,a_{2n+1}$ 中两项的差的正整数。可以证明，任意一个正整数都能唯一的表示为数列 $a$ 中两项的差 $a_p-a_q$。给定 $n$ ($1\le n\le 10^5$) 个正整数 $x$ ($1\le x\le 10^9$)，求出这个表示。

题解

由于 $a_{56}=1062283805$, $a_{57}=2a_{56}$，在这之后所有不超过 $10^9$ 的差都是 $a_{2n+2}-a_{2n+1}$ 的形式。那么求出所有 $1\le q< p\le 56$ 的答案，所有不在这些当中的数会以 $a_{58}-a_{57},a_{60}-a_{59},\ldots$ 的形式依次出现。因此每次询问二分即可。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
constexpr int A[] = {0, 1, 2, 4, 8, 16, 21, 42, 51, 102, 112, 224, 235, 470, 486, 972, 990, 1980, 2002, 4004, 4027, 8054, 8078, 16156, 16181, 32362, 32389, 64778, 64806, 129612, 129641, 259282, 259313, 518626, 518658, 1037316, 1037349, 2074698, 2074734, 4149468, 4149505, 8299010, 8299049, 16598098, 16598140, 33196280, 33196324, 66392648, 66392693, 132785386, 132785432, 265570864, 265570912, 531141824, 531141876, 1062283752, 1062283805};
std::vector<std::tuple<int, int, int>> ans;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    for (int i = 1; i <= 56; ++i)
        for (int j = 1; j < i; ++j)
            if (A[i] - A[j] <= 1e9)
                ans.emplace_back(A[i] - A[j], i, j);
    std::sort(ans.begin(), ans.end());
    int t;
    std::cin >> t;
    while (t--) {
        int x;
        std::cin >> x;
        int k = std::lower_bound(ans.begin(), ans.end(), std::make_tuple(x + 1, 0, 0)) - ans.begin() - 1;
        auto [y, p, q] = ans[k];
        if (x != y) {
            p = 2 * (x - k + 27);
            q = p - 1;
        }
        std::cout << p << " " << q << "\n";
    }
    return 0;
}