本蒟蒻的第一篇题解

题面

题目描述

任何一个正整数都可以用 $2$ 的幂次方表示。例如 $137=2^7+2^3+2^0 $。

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

由此可知，$137$ 可表示为 $2(7)+2(3)+2(0)$

进一步：

$7= 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$ 表示（在表示中不能有空格）。

样例 #1

样例输入 #1

1
1315

样例输出 #1

1
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

提示

【数据范围】

对于 $100\%$ 的数据，$1 \le n \le 2 \times {10}^4$。

NOIP1998 普及组 第三题

题解

对于一个正整数 $n$, 容易将其分解为 $2^a+2^b+···+2^c+(1)$(若数 $n$ 为奇数)

举个栗子，对于一个正整数 $23$, 可将其分解为 $2^4+2^2+2+1$
由于 $1$ 可以表达为 $2^0$
故原式可表达为 $2^4+2^2+2+2^0$
根据题意 指数也许进一步分解
故结果为 $2^{2^2}+2^2+2+2^0$

我们不难发现，分解出的指数还要继续分解，是重复的但规模更小的问题。故用到的方法是是递归/分治

话不多说，上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n =int(input())

def change(num):
    if num == 2:
        return "2"
    elif num == 1:
        return "2(0)" #边界
    else:
        i = 0
        while True:
            i+=1
            if 2**i == num:
                return "2("+change(i)+")" #一个补丁，当num被分解为2**1+n时,1会被分解为2(0),而实际上1应该省略
            elif 2**i >num:
                if i==2:
                    return "2+" + change(num - (2 ** (i - 1)))
                else:
                    return "2("+change(i-1)+")+"+change(num-(2**(i-1)))
print(change(n))