目录

题目描述

输入格式

输出格式

输入输出样例

输入#1

输出#1

输入#2

输出#2

数据范围

解题思路

代码

题目描述

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

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

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

进一步：

7= 2^2+2+2^07=22+2+20 ( 2^121 用 22 表示)，并且 3=2+2^03=2+20。

所以最后 137137 可表示为 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=2^{10} +2^8 +2^5 +2+11315=210+28+25+2+1

所以 13151315 最后可表示为 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)。

输入格式

一行一个正整数 nn。

输出格式

符合约定的 nn 的 0, 20,2 表示（在表示中不能有空格）。

输入输出样例

输入#1

1315

输出#1

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

输入#2

1

输出#2

2（0）

数据范围

对于 100\%100% 的数据，1 \le n \le 2 \times {10}^41≤n≤2×104。

解题思路

看到这道题，大家的思路一般都是递归吧。

就是把n分成一个多项式。然后又把每一项的幂次再分成一个多项式，那么判定终止条件是什莫呢？我们在分解的时候只要n等于0了，就代表这一项不能再继续分解为多项式了，对于任意一项，它的幂次要么是0、1、2，1的话是可以省略的，所以最终的表达式就只有0和2了，所以我们在分解幂次的时候判定条件是他要大于2，我的代码里面i就代表这一项的幂次，i>2,分解i，<=2的时候就输出，输出时再判定一下i是否等于1，不等于就输出i，等于就直接下一项。在输出格式的时候也要注意i和n的大小，n等于0就代表这一个多项式分解到头了，结尾的时候不应该加上“+”，i=1的话，就代表1这个幂次要被省略，开头和结尾不应该带“（）”，说的有点乱，总的就是把，系数和幂次都分解为多项式，多项式的规定就是幂次只能为0、1、2，1要省略，和格式要求，题不难，那就是要有耐心。

代码

import java.util.Scanner;public class 幂次方 {static int n;public static void main(String[] args) {Scanner sc=new Scanner(System.in);n=sc.nextInt();f(n);}private static void f(int n) {int m=1,i=0;while(mn) {i--;n-=(m/2);}else {n-=m;}if(i!=1) {System.out.print("2(");}else {System.out.print("2");}if(i>2) {f(i);}else {if(i!=1) {System.out.print(i);}}if(i!=1) {if(n!=0) {System.out.print(")+");}else {System.out.print(")");}}else {if(n!=0) System.out.print("+");}if(n>0) {f(n);}}}