定义α(n):α 为阿克曼函数的反函数，即为最大的整数 m 使得 akm(m,m)⩽n。 输入 n，请输出α(n) 的值，即满足akm(m,m)≤n 的最大的 m 值。O(logN)

阿克曼函数 (Ackermann function) 是一个非常著名的数学函数，它在计算理论中有重要应用。阿克曼函数 `A(m, n)` 定义如下：

- 如果 `m = 0`，则 `A(m, n) = n + 1`
- 如果 `m > 0` 且 `n = 0`，则 `A(m, n) = A(m - 1, 1)`
- 如果 `m > 0` 且 `n > 0`，则 `A(m, n) = A(m - 1, A(m, n - 1))`

要找到阿克曼函数的反函数，即 `α(n)`，我们需要寻找最大的整数 `m` 使得 `A(m, m) ≤ n`。

由于阿克曼函数的增长速度极快（比指数级还快），对于较大的 `n`，直接计算 `A(m, m)` 非常困难，尤其是当 `m` 本身也较大时。但是，可以通过观察阿克曼函数的增长模式来设计一个近似算法，因为 `A(m, m)` 的增长速度实际上是递减的。

为了达到 O(logN) 的时间复杂度，我们可以采用二分查找的思想。首先猜测一个中间值 `m`，然后检查 `A(m, m)` 是否小于或等于 `n`。如果大于，则在左半区间继续搜索；如果小于或等于，就在右半区间继续搜索。每次都将搜索范围减半，直到找到满足条件的最大 `m` 或者搜索范围变得足够小。

以下是一个简单的 C++ 实现，使用了迭代而不是递归以避免栈溢出的问题：

#include <iostream>

// 用表格存储已计算过的阿克曼函数值，用于优化性能
std::vector<std::pair<int, int>> ak_table;

int ackermann(int m, int n)
{
    // 初始化阿克曼表，存储已经计算过的结果
    if (m == 0 || n == 0) {
        return m + n;
    }
    auto it = std::lower_bound(ak_table.begin(), ak_table.end(), std::make_pair(m, n));
    if (it != ak_table.end() && it->first == m && it->second == n) {
        return it- 1, ackermann(m, n - 1));
    ak_table.push_back(std::make_pair(m, n));
    return result;
}

int alpha(int n)
{
    int low = 0;
    int high = 5; // 初始猜测为不大于5的整数
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int value = ackermann(mid, mid);
        if (value <= n) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low - 1; // 减一是因为数组下标从0开始
}

int main()
{
    int n;
    std::cin >> n;
    std::cout << "α(" << n << ") = " << alpha(n) << std::endl;
    return 0;
}