2481: 【普及-】【P1010】幂次方

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：3 解决：1

题目描述

任何一个正整数都可以用 lns="http://www.w3.org/1998/Math/MathML">2 的幂次方表示。例如 lns="http://www.w3.org/1998/Math/MathML">137=27+23+20。

同时约定方次用括号来表示，即 lns="http://www.w3.org/1998/Math/MathML">�� 可表示为 lns="http://www.w3.org/1998/Math/MathML">�(�)。

由此可知，lns="http://www.w3.org/1998/Math/MathML">137 可表示为 lns="http://www.w3.org/1998/Math/MathML">2(7)+2(3)+2(0)

进一步：

lns="http://www.w3.org/1998/Math/MathML">7=22+2+20 ( lns="http://www.w3.org/1998/Math/MathML">21 用 lns="http://www.w3.org/1998/Math/MathML">2 表示)，并且 lns="http://www.w3.org/1998/Math/MathML">3=2+20。

所以最后 lns="http://www.w3.org/1998/Math/MathML">137 可表示为 lns="http://www.w3.org/1998/Math/MathML">2(2(2)+2+2(0))+2(2+2(0))+2(0)。

又如 lns="http://www.w3.org/1998/Math/MathML">1315=210+28+25+2+1

所以 lns="http://www.w3.org/1998/Math/MathML">1315 最后可表示为 lns="http://www.w3.org/1998/Math/MathML">2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)。

输入

一行一个正整数 lns="http://www.w3.org/1998/Math/MathML">�。

输出

符合约定的 lns="http://www.w3.org/1998/Math/MathML">� 的 lns="http://www.w3.org/1998/Math/MathML">0,2 表示（在表示中不能有空格）。

样例输入 复制 

1315

样例输出 复制 

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

提示

对于 lns="http://www.w3.org/1998/Math/MathML">100% 的数据，lns="http://www.w3.org/1998/Math/MathML">1≤�≤2×104。 

#include<bits/stdc++.h>
using namespace std;

string expand(int x) {
	if (x==1) return "2(0)";
	else if (x==2) return "2";
	else if (x==3) return expand(2) +"+"+expand(1);
	int b=(int)log2(x);
	if (log2(x)==b)
		return "2("+expand(b) +")";
	else
	    return "2("+expand(b)+")+"+expand(x-(int)pow(2,b));
}

int main(){
    int n;
    cin>>n;
    cout<<expand(n)<<endl;
	return 0;
}

来源/分类

提交提交记录统计露一手!