算法题：幂次方

问题描述

任何一个正整数都可以用 2 的幂次方表示。例如 137=2⁷+2³+2⁰。

同时约定方次用括号来表示，即 a^b 可表示为 a(b)。

由此可知，137可表示为 2(7)+2(3)+2(0)2(7)+2(3)+2(0)
进一步：

7=2²+2+2⁰ ( 2¹ 用 2 表示)，并且 3=2+2⁰。

所以最后 137 可表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0)。

又如 1315=2¹⁰+2⁸+2⁵+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)

数据范围

1≤n≤2×10⁴

解决方案

思路

分治

代码

#include <iostream>

using namespace std;

void fun(int n) {
    if (n == 3) {
        cout << "2+2(0)";
        return;
    } else if (n == 2) {
        cout << 2;
        return;
    } else if (n == 1) {
        cout << "2(0)";
        return;
    }

    int m = 0;
    for (int i = 1; (1 << i) <= n; ++i) {
        m = i;
    }

    cout << "2(";
    fun(m);
    cout << ")";

    int t = n - (1 << m);
    if (t) {
        cout << "+";
        fun(t);
    }
}

int main() {
    int n;
    cin >> n;

    fun(n);

    return 0;
}