题意分析

Amtel公司每十年将计算机芯片的字长翻倍（如1960年4位，1970年8位，依此类推）。新的基准测试Factstone评级定义为最大的整数$n$，使得$n!$（$n$的阶乘）可以用当前字长的无符号整数表示。给定年份$y$（1960 ≤ $y$ ≤ 2160），需要计算对应的Factstone评级。

解题思路

1. 确定字长：
   根据年份$y$计算芯片的字长位数。每十年字长翻倍，公式为：

   $$\text{位数} = 2^{\frac{y - 1940}{10}}$$

   例如，1960年对应$2^2 = 4$位，2010年对应$2^7 = 128$位。

2. 计算可表示的最大值：
   字长为$w$位的无符号整数最大值为$2^w - 1$。题目需要找到最大的$n$使得$n! \leq 2^w - 1$。

3. 对数转换：
   直接计算大数值的阶乘会导致溢出，因此使用斯特林公式（Stirling's approximation）估算$n!$的自然对数：

   $$\ln(n!) \approx n \ln n - n + 0.5 \ln(2\pi n)$$

   同时，将$2^w$转换为对数形式：

   $$\ln(2^w) = w \ln 2$$

4. 预处理与二分查找：

   • 预处理所有可能的$n$对应的$\ln(n!)$值。
   • 对于每个查询，计算当前年份对应的$w \ln 2$，并通过二分查找找到满足$\ln(n!) \leq w \ln 2$的最大$n$。

示例代码

#include <iostream>
#include <cmath>
using namespace std;

const double PI = 3.1415926;
const int MAXN = 270005;
double lnN[MAXN];

// 预处理所有n的ln(n!)值
void init() {
    lnN[1] = 0;
    for (int i = 2; i < MAXN; i++) {
        lnN[i] = i * log(1.0 * i) - i + 0.5 * log(2.0 * i * PI);
    }
}

int main() {
    init();
    int y;
    while (cin >> y && y != 0) {
        double exponent = (y - 1940) / 10.0;
        double word_size = pow(2, exponent);
        double max_log = word_size * log(2.0);
        
        // 二分查找最大的n
        int left = 1, right = MAXN - 1, ans = 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (lnN[mid] <= max_log) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

注意事项

1. 数据范围：

   • 年份$y$的最大值为2160，对应字长为$2^{22} = 4194304$位，需要确保预处理数组足够大。

2. 精度问题：

   • 使用double类型存储对数结果，避免精度损失。斯特林公式在$n$较大时非常精确。

3. 二分查找优化：

   • 直接遍历查找可能超时，使用二分查找将时间复杂度从$O(n)$优化为$O(\log n)$。

4. 边界处理：

   • 预处理数组的大小需根据题目数据范围调整，确保覆盖所有可能的$n$值。

5. 输入输出格式：

   • 输入以0结束，每个测试用例输出一行结果。