欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

幂次方(洛谷-P1010)

程序员文章站 2022-05-08 22:13:33
...

题目描述

任何一个正整数都可以用 2 的幂次方表示。例如

137=2^7+2^3+2^0

同时约定方次用括号来表示,即 a^b 可表示为 a(b)。

由此可知, 137 可表示为:2(7)+2(3)+2(0)

进一步:7=2^2+2+2^0(2^1用2表示),并且 3=2+2^0

所以最后 137 可表示为:2(2(2)+2+2(0))+2(2+2(0))+2(0)

又如:1315=2^{10} +2^8 +2^5 +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)

源代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 100001
#define MOD 123
#define E 1e-6
using namespace std;
void calculate(int x)
{
    while(x>0)
    {
        int temp=1;//比a小的最大的2次方的数
        int index=0;//temp的指数
        while(x>=temp*2)//寻找temp与index
        {
            temp*=2;
            index++;
        }

        x-=temp;
        if(index==0)//2的零次方直接输出
             printf("2(%d)",index);
        else if(index==1)//2的1次方输出2
            cout<<2;
        else//都不是的话,对index进行递归
        {
            cout<<"2(";
            calculate(index);
            cout<<")";
        }
        if(x>0)//最后一位不输出加号
            cout<<"+";
    }
}
int main()
{
    int n;

    cin>>n;
    calculate(n);

    return 0;
}