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
using namespace std;
string ans;
string num(int n)
{string str;while (n > 0){if (n & 1)str += '1';elsestr += '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 << ")";}elsecout << 2;}}return;
}
int main()
{int a;cin >> a;if (a == 0)cout << 0;digui(a);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！