📝 题目大意

给定整数 $N$，判断是否存在正整数 $A, B$ 使得 $3^A + 5^B = N$。若存在输出任意一组 $(A, B)$，否则输出 $-1$。

💡 解题思路

1. 题目分析：$N$ 上限为 $10^{18}$，而 $3^A$ 和 $5^B$ 均是指数增长，因此 $A$ 和 $B$ 的取值上限非常小。具体地，$3^{38} \approx 1.35 \times 10^{18}$，$5^{26} \approx 1.49 \times 10^{18}$，所以 $A \leq 38$、$B \leq 26$。这意味着我们可以暴力枚举其中一个变量，再用哈希表快速查询另一个变量是否存在。

2. 算法推导：

   • 首先预处理出所有不超过 $N$ 的 $5$ 的幂 $5^B$（$B \geq 1$），将它们存入哈希表 mp，键为 $5^B$ 的值，值为对应的指数 $B$。
   • 然后枚举 $A$（$A \geq 1$），计算 $3^A$，并检查 $N - 3^A$ 是否在哈希表中。若存在，则找到一组解 $(A, B)$，直接输出并结束程序。
   • 这本质上是"枚举一个维度 + 哈希表查另一个维度"的双指针/预处理优化思路，将 $\Theta(A_{\max} \times B_{\max})$ 的双重循环降为 $\Theta(A_{\max} + B_{\max})$。
   • 代码中 mp 存储 5^B → B 的映射，while (mul * 5 <= n) 循环逐次生成 $5^1, 5^2, \dots$；同理，第二个 while (mul * 3 <= n) 枚举 $3^1, 3^2, \dots$，每次用 mp.count(n - mul) 判断差值是否为 $5$ 的幂。

3. 边界与细节：

   • $A$ 和 $B$ 均为正整数（$A \geq 1, B \geq 1$），因此代码中 cnt 初始为 $0$，先 cnt++ 再 mul *= 3/5，确保从 $3^1$、$5^1$ 开始枚举。
   • 当 $N$ 较小时（如 $N=1$），两个 while 循环均不会进入，mp 为空，程序直接输出 $-1$，这是正确的。
   • 使用 long long 避免中间计算溢出，$3^{38}$ 和 $5^{26}$ 均在 long long 范围内。

⏱️ 复杂度分析

• 时间复杂度：预处理 $5$ 的幂需要 $\Theta(\log_5 N)$ 次迭代，枚举 $3$ 的幂需要 $\Theta(\log_3 N)$ 次迭代，每次哈希表查询为 $O(1)$。总时间复杂度为 $O(\log N)$。
• 空间复杂度：哈希表 mp 存储最多 $\log_5 N$ 个键值对，空间复杂度为 $O(\log N)$。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL n;
// mp: 存储 5^B -> B 的映射
map<LL, int> mp;
int main(){
	cin >> n;
	// 预处理所有不超过 n 的 5 的幂
	int cnt = 0;
	LL mul = 1;
	while (mul * 5 <= n){
		cnt++;         // B 从 1 开始
		mul *= 5;      // mul = 5^cnt
		mp[mul] = cnt; // 记录 5^cnt 对应的指数
	}
	// 枚举 3^A，检查 n - 3^A 是否为 5 的幂
	mul = 1, cnt = 0;
	while (mul * 3 <= n){
		cnt++;         // A 从 1 开始
		mul *= 3;      // mul = 3^cnt
		if (mp.count(n - mul)){ // 差值 n - 3^A 是 5 的某次幂
			cout << cnt << ' ' << mp[n - mul] << '\n';
			return 0;
		}
	}
	// 无解
	cout << "-1\n";
	return 0;
}