题解

思路

正指数下，$3^A$ 和 $5^B$ 都从各自的底数开始，并且随指数严格增大。

做法

分别不断乘以 $3$ 和 $5$，枚举所有不超过 $N$ 的幂；对每一对幂检查它们的和是否等于 $N$。一旦相等就输出对应指数，全部检查后仍未找到则输出 -1。

复杂度

因为 $3^A\le 10^{18}$ 时指数只有 $O(\log_3 N)$ 种，$5^B$ 也只有 $O(\log_5 N)$ 种，所以时间复杂度为 $O(\log_3 N\log_5 N)$，空间复杂度为 $O(1)$。乘法与求和使用足够宽的整数类型，避免接近 $10^{18}$ 时溢出。