题目描述
任何一个正整数都可以用222的幂次方表示。例如
137=27+23+20137=2^7+2^3+2^0 137=27+23+20
同时约定方次用括号来表示，即aba^bab 可表示为a(b)a(b)a(b)。
由此可知，137137137可表示为：
2(7)+2(3)+2(0)2(7)+2(3)+2(0)2(7)+2(3)+2(0)
进一步：
7=22+2+207= 2^2+2+2^07=22+2+20 (2^1用2表示)，并且
3=2+203=2+2^03=2+20
所以最后137137137可表示为：
2(2(2)+2+2(0))+2(2+2(0))+2(0)2(2(2)+2+2(0))+2(2+2(0))+2(0)2(2(2)+2+2(0))+2(2+2(0))+2(0)
又如：
1315=210+28+25+2+11315=2^{10} +2^8 +2^5 +2+11315=210+28+25+2+1
所以131513151315最后可表示为：
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
输入输出格式
输入格式：
一个正整数n(n≤20000)n(n≤20000)n(n≤20000)。
输出格式：
符合约定的nnn的0,20,20,2表示(在表示中不能有空格)
输入输出样例
输入样例#1：
1315
输出样例#1：
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
分析：分治，将大问题化为若干个规模相近的小问题。。。从而分而治之。
1 #include<iostream> 2 using namespace std; 3 int x; 4 5 int cf(int a,int b){//由于cmath的pow在这里不好用，就手写了一个计算乘方的函数。 6 int z=1; 7 for(int i=0; i<b; i++ ){ 8 z*=a; 9 } 10 return z; 11 } 12 13 void digui(int n){ 14 int y; 15 if(n==0) return ; 16 for(int i=0; i<=15; i++ ){ 17 y=i; 18 if(cf(2,i)>n){ 19 y--; 20 break; 21 } 22 } 23 if(y==0) cout<<"2(0)"; 24 if(y==1) cout<<"2"; 25 if(y>1){ 26 cout<<"2("; 27 digui(y); 28 cout<<")"; 29 } 30 if(n!=cf(2,y)){ 31 cout<<"+"; 32 digui(n-cf(2,y)); 33 } 34 } 35 int main(){ 36 cin>>x; 37 digui(x); 38 return 0; 39 }
另外：附加一位不知名的OIer的神奇的代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 string run(int x,int i=0,string s=string("")){ 4 if(x==0)return string("0"); 5 do 6 if(x&1)s=(i==1?"2":"2("+run(i)+")")+(s==""?"":"+")+s;//拼接字符串，应题意，要把低次方接在后面 7 while(++i,x>>=1);//每次向右移位 8 return s; 9 } 10 int main(){ 11 int x;cin>>x; 12 cout<<run(x)<<endl; 13 }