博主主页：Yu·仙笙

专栏地址：洛谷千题详解

目录

题目描述

输入格式

输出格式

输入输出样例

解析： 

C++源码：

Pascal源码：

Java源码：

Python源码：

---

------------------------------------------------------------------------------------------------------------------------------- 

 -------------------------------------------------------------------------------------------------------------------------------

题目描述

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

同时约定方次用括号来表示，即 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

1315

输出 #1

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

 -------------------------------------------------------------------------------------------------------------------------------

解析： 

我们知道，二进制数表示的其实就是一个正整数分解成为2的幂次方和！

如3用二进制表示为 11 ,从右到左分别是第0位，第1位……

则3=2^1+2^0(只要二进制那位是一，就是2^（这一位）)

再比如10 二进制是1010，则10=2^3+2^1;

大家自己体会一下

下面更高级的：位运算（其实也不高级，就是没人做）

不会位运算的就用上面那种吧，个人觉得位运算更快（普通14ms，位运算11ms）

位运算具体问度娘吧

思路如下：

遍历n的二进制（从地位到高位），用数组储存该位为1的位数；如1010（即10），先记录第1位是1，最后记录到第3位是1；

遍历完成后，对高位先进行处理（即原来为i++，现在变为i--）

该位(就是幂的次数)大于2,，递归再次处理

一旦处理到该位小于3，输出；

 -------------------------------------------------------------------------------------------------------------------------------

C++源码：

#include
using namespace std;
void ASCII(int m)
{int i=0,k=m,u=0,h[50];while(k)//位运算实现；{if(k&1)h[++u]=i;//h[++u]相当于++u，h[u]…… k>>=1;i++;}//据上面写的，u从1开始，无论如何一定会有输出； while(u)//u为真 {if(h[u]<3)//具体括号判断；{if(h[u]==1 && u-1!=0)  printf("2+");else if(h[u]==1)	   printf("2");if((h[u]==0||h[u]==2)&&(u-1!=0))  printf("2(%d)+",h[u]);else if(h[u]==0||h[u]==2)		  printf("2(%d)",h[u]);	--u;//搜索下一个；}else{printf("2(");ASCII(h[u--]);//相当于h[u],--u; //这里千万不能写成 h[--u],否则你会3个WA两个MLE； if(u!=0)printf(")+");//由于u进行了自减，此时的u已经是下一个数了； else printf(")");//判断括号；}	}
}
int main()
{int n;scanf("%d",&n);ASCII(n);return 0;//别忘了写；
}

  -------------------------------------------------------------------------------------------------------------------------------

Pascal源码：

type num=array[0..100000] of longint;
var i,j,k,l,n,m,o,p,h:longint;
//这里的a[0]指数组长度。
function ejz(s:longint):num;//要转的数
var i,j,k:longint;ans:num;
begin  i:=s; j:=0; k:=0; //让变量i赋值为要转的数sfillchar(ejz,sizeof(ejz),0);fillchar(ans,sizeof(ans),0);while i>0 dobegininc(j);ejz[j]:=i mod 2;i:=i div 2;  //转2进制的过程在此。end;for i:=j downto 1 doif ejz[i]=1 then begin inc(k); ans[k]:=i-1; end;//若2进制的第n位为1，那么数组中必有n-1。这个应该知道吧ans[0]:=k;exit(ans);
end;
procedure search(a:longint);
var n:num; i:longint;
beginif a=0 then begin write('2(0)'); exit; end; //如果要处理0，那么...if a=1 then begin write('2'); exit; end;    //如果要处理1，那么...n:=ejz(a);for i:=1 to n[0]-1 dobeginif (n[i]<>1) and (n[i]<>0) then write('2(');//这里要注意了!2^1不是2(1)!!!search(n[i]);//递归处理数组里的数if (n[i]<>1) and (n[i]<>0) then write(')');write('+');//不要把加号输多了!end;if (n[n[0]]<>1) and (n[n[0]]<>0) then write('2(');search(n[n[0]]);if (n[n[0]]<>1) and (n[n[0]]<>0) then write(')');
end;
beginreadln(n);search(n);
end.

  -------------------------------------------------------------------------------------------------------------------------------

Java源码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc= new Scanner(System.in);int a=sc.nextInt();pow(a);}public static void pow(int a){if(a>3){int s=0;int b=2;while(b<=a){b=b*2;s++;}a=a-b/2;System.out.print("2(");pow(s);if(s==3){System.out.print("2+2(0)");}if(s==1){System.out.print("2(0)");}if(s==2){System.out.print("2");}System.out.print(")");if(a==3){System.out.print("+2+2(0)");}if(a==1){System.out.print("+2(0)");}if(a==2){System.out.print("+2");}if(a>3){System.out.print("+");}pow(a);}}
}

  -------------------------------------------------------------------------------------------------------------------------------

Python源码：

def f1(x):##获取一个数的幂str0 = bin(int(str(x), 10))str1 = str0[2:]list1 = []index = 0for i in str1[::-1]:if i == '1':list1.append(index)index += 1list1.reverse()return list1
def f2(list):##格式化输出list1 = [str(i) for i in list]str2 = ''for i in range(len(list1)):if i < len(list1) - 1:if list1[i] == "1":str2 += "2+"else:if list[i] != 0:str2 += "2({})+".format(f2(f1(list[i])))else:str2 += "2(0)"if i == len(list1) - 1:if list1[i] == "1":str2 += "2"else:if list[i] != 0:str2 += "2({})".format(f2(f1(list[i])))else:str2 += "2(0)"return str2n=int(input())
print(f2(f1(n)))

  -------------------------------------------------------------------------------------------------------------------------------