集训作业 洛谷P1010 幂次方

这个……

这个题看上去有点难的样子。

仔细看看，感觉有点简单。啊，是递归啊，正经的看一看，好像是把一个数分成2的几次方的和。

然后余数和比他小的最大的2的次方数如果不是2的一次方或者2的0次方，就继续递归。

仔细一想貌似很简单，只不过余数是在括号外面，商是在里面的，这种小事稍微写写就可以了。

直接代码吧，这题除了题意有点复杂以外还行……

#include<iostream>
#include<cstdio>
using namespace std;
long long m;
long long sz[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};//电脑打的表，这个比无数次pow快多了
void dg(int n)
{
	while(n!=0)//这整个循环是把n的余数继续拆。
	{
		for(int i=15;i>=0;i--)//这个是查看比他小的最大的2的次方数
		{
			if(sz[i]<=n)
			{
				n-=sz[i];
				if(i==1)//这说明n是2或者3，反正都不需要括号
				{
					cout<<"2";
				}else if(i==0)//这说明n就是1
				{
					cout<<"2(0)";
				}else//这个需要括号，继续继续这里继续的是次方数
				{
					cout<<"2(";
					dg(i);
					cout<<")";
				}
				break;
			}
		} 
		if(n!=0)//后面还有余数，写个+
		{
			cout<<"+";
		}
	}
}
int main()
{
	scanf("%lld",&m);
	dg(m);
	return 0;
}

这个还是很好理解的吧，不理解的请去看看样例读读题。