NOIP1998普及组复赛第二题 贰的幂方 解题报告

【问题描述】  
  
任何一个正整数都可以用 2 的幂次方表示。例如:137=27+23+20。
　　在这里我们约定次方用括号来表示，即 ab 可表示为 a(b)。
　　由上面叙述可知：137 又可以表示为 2(7)+2(3)+2(0)。进一步：7=22+2+20=2(2)+2+2(0)(21用2表示)。3=2+20=2+2(0)。所以最后137可表示为:2(2(2)+2+2(0))+2(2+2(0))+2(0)。
　　又如:1315=210+28+25+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 表示(在表示中不能有空格)。


 【输入样例】   
   
137
1315


【输出样例】  
   
2(2(2)+2+2(0))+2(2+2(0))+2(0)
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)


【数据范围】  
   
n <= 2^31

 【来源】  
  
NOIP1998普及组复赛第二题

 解题思路：本题的主要算法为分治算法，对于每输入一个数，我们可以先把它分解为2的幂方的和，然后将指数大于2的继续分解。需要注意的是，本题中n的范围最大为2^31，超过了int的范围（2^31-1），所以n定义为long long，并且，在计算2^31时，要么直接用1<<31然后强制类型转换为long long，要么可以先计算出1<<30，再将得到的值乘2。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=35;
long long N;  //定义为long long
void solve(long long x)
{
	int ok=0;  //用来记录是否已经输出过值，以控制输出'+'
	for(int i=31;i>=0;i--)
	{
		long long k;
		if(i<31)  k=1<<i;
		else  //计算2^31
		{
			k=1<<30;
			k=k*2;
		}
		if(x>=k && i>2) 
		{
			if(ok==1)  printf("+");  
			printf("2(");
			solve(i);  //指数大于2，继续分解
			printf(")");
			ok=1;
			x-=k;
		}
		if(x>=k && i==2)  
		{
			if(ok==1)  printf("+");
			printf("2(2)");
			ok=1;
			x-=k;
		}
		if(x>=k && i==1)
		{
			if(ok==1)  printf("+");
			printf("2");
			ok=1;
			x-=k;
		}
		if(x>=k && i==0)
		{
			if(ok==1)  printf("+");
			printf("2(0)");
			ok=1;
			x-=k;
		}
	}
}
int main()
{
	freopen("48.in","r",stdin);
	//freopen("48.out","w",stdout);
	while(cin>>N)  
	{
		solve(N);
		printf("\n");
	}
	return 0;
}