P1010 幂次方(C++_数论_分治)

题目描述

任何一个正整数都可以用22的幂次方表示。例如
137=2⁷+2³+2⁰同时约定方次用括号来表示，即a^b可表示为a^b。
由此可知，137可表示为：
2(7)+2(3)+2(0)
进一步：
7= 2²+2+2⁰(2¹用2表示)，并且 3=2+2⁰
所以最后137可表示为：
2(2(2)+2+2(0))+2(2+2(0))+2(0)
又如：
1315=2¹⁰+2⁸ +2⁵ +2+1
所以1315最后可表示为：
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

输入格式

一个正整数n(n≤20000)。

输出格式

符合约定的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)

反思

对分治递归还是很不习惯emmmmmm

源码

#include<bits/stdc++.h>
using namespace std;
string ans;
string num(int n)
{
	string str;
	while (n > 0)
	{
		if (n & 1)
			str += '1';
		else
			str += '0';
		n >>= 1;
	}
	return str;
}
void digui(int a)
{
	if (a == 0)
	{
		cout << 0;
		return;
	}
	if (a == 2)
	{
		cout << 2;
		return;
	}
	bool flag = 0;
	string str=num(a);
	for (int i = str.length() - 1; i >= 0; i--)
	{
		if (str[i] == '1')
		{
			if (flag == 1)
				cout << "+";
			flag = 1;
			if (i != 1)
			{
				cout << 2 << "(";
				digui(i);
				cout << ")";
			}
			else
				cout << 2;
		}
	}
	return;
}
int main()
{
	int a;
	cin >> a;
	if (a == 0)
		cout << 0;
	digui(a);
	return 0;
}