题目解析

问题重述

初始有一枚价值为 $n$ 的硬币。每次操作可以选择一枚价值 $x > 3$ 的硬币，将其替换为两枚价值为 $\lfloor x/4 \rfloor$ 的硬币。问经过任意次操作后，最多能获得多少枚硬币。

核心思路

1. 贪心策略

由于每次操作都会增加硬币总数（$1$ 枚变成 $2$ 枚），只要存在价值 $>3$ 的硬币，我们就应该进行操作。因为操作只会让硬币价值变小，不会产生负面影响，且能增加数量。

2. 批量操作优化

如果一枚价值为 $x$ 的硬币可以进行 $k$ 次操作，那么：

• 第 $1$ 次操作后：$2$ 枚价值 $\lfloor x/4 \rfloor$ 的硬币
• 第 $2$ 次操作后：$4$ 枚价值 $\lfloor x/16 \rfloor$ 的硬币
• 第 $3$ 次操作后：$8$ 枚价值 $\lfloor x/64 \rfloor$ 的硬币
• ……
• 第 $k$ 次操作后：$2^k$ 枚价值 $\lfloor x/4^k \rfloor$ 的硬币

因此，我们不需要模拟每次操作处理一枚硬币，而是可以一次性处理所有同价值的硬币。

3. 算法流程

设当前硬币价值为 $v$，硬币数量为 $cnt$：

• 初始：$v = n$，$cnt = 1$
• 当 $v > 3$ 时：
  • 将所有价值为 $v$ 的硬币各操作一次
  • 每枚价值 $v$ 的硬币变成 $2$ 枚价值 $\lfloor v/4 \rfloor$ 的硬币
  • 因此：$cnt \leftarrow cnt \times 2$，$v \leftarrow \lfloor v/4 \rfloor$
• 最终答案为 $cnt$

这个过程可以用一个简单循环实现：

ans = 1
while n > 3:
    n //= 4
    ans *= 2

4. 数学公式

设 $k$ 为满足 $\lfloor n/4^k \rfloor \le 3$ 的最小整数，即不断除以 $4$ 直到值 $\le 3$ 的次数。

则答案为：

$$\text{ans} = 2^k$$

其中 $k = \max\{t \mid 4^t \le n\}$，即 $k = \lfloor \log_4 n \rfloor$。

注意： 使用浮点数对数函数可能产生精度问题，因为 $n$ 最大为 $10^{18}$，浮点数精度不足以精确表示。推荐使用迭代或二分法求 $k$。

示例验证

示例1： $n = 1$

• $1 \le 3$，循环不执行
• $ans = 1$ ✅

示例2： $n = 5$

• 第1次：$n = 5/4 = 1$，$ans = 2$
• $1 \le 3$，停止
• $ans = 2$ ✅

示例3： $n = 16$

• 第1次：$n = 16/4 = 4$，$ans = 2$
• 第2次：$n = 4/4 = 1$，$ans = 4$
• $1 \le 3$，停止
• $ans = 4$ ✅

示例4： $n = 10^{18}$

• $4^{29} \approx 2.88 \times 10^{17} \le 10^{18}$
• $4^{30} \approx 1.15 \times 10^{18} > 10^{18}$
• 循环执行 $29$ 次
• $ans = 2^{29} = 536870912$ ✅

时间复杂度

• 每次循环 $n$ 除以 $4$，最多 $\lfloor \log_4 n \rfloor + 1$ 次
• $n \le 10^{18}$ 时，最多约 $30$ 次循环
• $t \le 10^4$，总操作次数约 $3 \times 10^5$，非常快

注意事项

1. 数据类型： 使用 long long 存储 $n$，因为 $n \le 10^{18}$ 超出 int 范围
2. 避免浮点数： 不要使用 log() 函数，可能产生精度误差
3. 循环条件： while (n > 3) 而不是 while (n > 0)，因为 $n \le 3$ 时无法操作

公式推导

从递推式出发：

$$f(x) = \begin{cases} 1 & x \le 3 \\ 2 \cdot f(\lfloor x/4 \rfloor) & x > 3 \end{cases}$$

展开得：

$$f(n) = 2 \cdot f(\lfloor n/4 \rfloor) = 2^2 \cdot f(\lfloor n/16 \rfloor) = \cdots = 2^k \cdot f(\lfloor n/4^k \rfloor) $$

当 $4^k > n$ 时，$\lfloor n/4^k \rfloor = 0 \le 3$，此时 $f(\lfloor n/4^k \rfloor) = 1$。

所以 $k = \lfloor \log_4 n \rfloor$，$f(n) = 2^{\lfloor \log_4 n \rfloor}$。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        long long n;
        cin >> n;
        
        long long ans = 1;
        while (n > 3) {
            n /= 4;      // 价值变为原来的 1/4
            ans *= 2;    // 硬币数量翻倍
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}

递归版本（仅供参考）

#include <bits/stdc++.h>
using namespace std;

long long solve(long long n) {
    if (n <= 3) return 1;
    return 2 * solve(n / 4);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        long long n;
        cin >> n;
        cout << solve(n) << '\n';
    }
    
    return 0;
}

二分查找版本（求 $\lfloor \log_4 n \rfloor$）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        long long n;
        cin >> n;
        
        // 二分查找最大的 k 使得 4^k <= n
        int k = 0;
        long long p = 1;  // p = 4^k
        while (p * 4 <= n) {
            p *= 4;
            k++;
        }
        
        // 或者直接用循环计算
        // int k = 0;
        // while ((1LL << (2 * k)) <= n) k++;  // 4^k = 2^(2k)
        // k--;  // 调整
        
        long long ans = 1LL << k;  // 2^k
        cout << ans << '\n';
    }
    
    return 0;
}

关键点总结

1. 贪心正确性： 只要 $x > 3$，操作一定增加硬币数，且不会阻碍后续操作
2. 批量处理： 所有同价值硬币可以同时操作，简化模拟过程
3. 循环次数： 约 $\log_4 n \le 30$ 次，非常高效
4. 整数运算： 全程使用整数除法和乘法，避免浮点数精度问题
5. 边界条件： $n \le 3$ 时无法操作，答案为 $1$