acwing 3483
wdxt 2021-06-04 10:25:03

acwing 3483.2 Power square

Every positive number can be expressed exponentially .

for example ,137=27+23+20.

Let's use it a(b) To express ab.

that 137 It can be expressed as 2(7)+2(3)+2(0).

because 7=22+2+20,3=2+20, therefore 137 In the end, it can be expressed as 2(2(2)+2+2(0))+2(2+2(0))+2(0).

Give a positive number n, Would you please n Expressed as containing only 0 and 2 The exponential form of .

Input format

The input contains multiple sets of data .

Each group of data occupies one row , A positive number n.

Output format

Output one row per group of data , An exponential representation of .

Data range

1≤n≤20000,
Each input contains at most 100 Group data .

1315

sample output ：

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

Ideas ：
1315=2(7)+2(3)+2(0), Find out 1315 Of 2 And then we have to find one of them 2 The combination of indices of , Then add them to the brackets in turn, so you can find them recursively .

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
string dfs(int x)
{
string res;
for(int i = 14; i >= 0; i --) // Because the maximum is 20000, So at most 2 Of 14 Power
{
if(x >> i & 1)// Judge x At the top of the table , then i That's one of them 2 The index of
{
if(res.size()) res += '+';// In no way 1 Use + Connection No
if(!i) res += "2(0)";// If 0 If you want to add 2(0)
else if(i == 1) res += "2";// If 1 Just add 2
else res += "2(" + dfs(i) + ")";// If not for 0 perhaps 1 So it's me
// We can decompose the index again , use 2(dfs(i)) In this form , take i The decomposed string is added to the answer .
}
}
return res;
}
int main()
{
int n;
while(cin >> n)
{
cout << dfs(n) << endl;
}
return 0;
}