【题目来源】
洛谷：P1010 [NOIP 1998 普及组] 幂次方 - 洛谷 (luogu.com.cn)
【题目描述】
任何一个正整数都可以用 \(2\) 的幂次方表示。例如 \(137=2^7+2^3+2^0\)。
同时约定次方用括号来表示，即 \(a^b\) 可表示为 \(a\)\((\)\(b\)\()\)。
由此可知，\(137\) 可表示为 \(2(7)+2(3)+2(0)\)
进一步：
\(7=2^2+2^2+2^0\) ( \(2^1\)用\(2\)表示），并且\(3=2+2^0\)。
所以最后 \(137\) 可表示为 \(2(2(2)+2+2(0))+2(2+2(0))+2(0)\)。
又如 \(1315=2^{10}+2^8+2^5+2+1\)
所以 \(1315\) 最后可表示为 \(2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)\)。
【输入】
一行一个正整数 \(n\)。
【输出】
符合约定的 \(n\) 的 \(0,2\) 表示（在表示中不能有空格）。
【输入样例】
1315
【输出样例】
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
【解题思路】
【算法标签】
《洛谷 P1010 幂次方》 #数学# #分治# #NOIP普及组# #1998#
【代码详解】
#include <bits/stdc++.h> // 包含标准库头文件
using namespace std;int mark[20] = {1}; // 存储2的幂次方值，初始化为1（2^0）// 递归函数，将数字n表示为2的幂次方和的形式
void f(int n)
{int flag = 0; // 用于标记最大的幂次// 找到不超过n的最大2的幂次方while (n >= mark[flag]) flag++;flag--; // 回退到合适的幂次// 根据不同的幂次进行输出if (flag == 1) cout << "2"; // 2^1直接输出2else {if (flag == 0) cout << "2(0)"; // 2^0输出2(0)else {cout << "2("; // 更高次幂需要递归处理f(flag); // 递归处理幂次cout << ")";}}// 减去已处理的部分，继续处理剩余数值n -= mark[flag];if (n != 0) {cout << "+"; // 还有剩余数值时输出加号f(n); // 递归处理剩余部分}
}int main()
{int n; // 输入的数字cin >> n;// 预计算2的0到16次方for (int i = 1; i < 17; i++) mark[i] = mark[i - 1] * 2;// 调用递归函数进行分解f(n);return 0; // 程序正常结束
}
【运行结果】
137
2(2(2)+2+2(0))+2(2+2(0))+2(0)