洛谷 P1010 幂次方 分治 递归

洛谷 P1010 幂次方 分治 递归

题解：

我们需要把数n不断地进行分解，直到所有的求和因数都是2的幂次方。所以我们递归分解即可。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<map>
#define MAX 500005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int a;

int q_pow(int a,int b){//a的b次方
    int ans=1;
    while(b>0){
        if(b&1){
            ans=ans*a;
        }
        a=a*a;
        b>>=1;
    }
    return ans;
}

void dfs(int n){
    if(n==0){//当n被全部分解为0
        return;
    }
    int tmp;
    for(int i=0;i<=15;i++){
        tmp=i;
        if(q_pow(2,i)>n){//找到第一个大于n的2的幂次数
            tmp--;
            break;
        }
    }
    if(tmp==0){//输出2的0次方
        printf("2(0)");
    }else if(tmp==1){//输出2的1次方
        printf("2");
    }
    if(tmp>1){//当次方大于1时
        printf("2(");//添加2
        dfs(tmp);
        printf(")");//结尾补括号
    }
    if(n!=q_pow(2,tmp)){//当n不等于2的tmp次方时
        printf("+");//添加+号
        dfs(n-q_pow(2,tmp));//递归剩余的
    }
}


int main(){
    scanf("%d",&a);
    dfs(a);
    return 0;
}