NOIPpj1998幂次方

P1010 幂次方

题解

这是一道比较麻烦的题，考的是分治和数学？？。

我们说现需要明确的一点是任何一个数都可以被2的幂次方表示，所以不存在无解的情况。

有没有发现计算机内部也是用2的幂次方表示一个数的，所以我们可以使用二进制。但我并不会。所以我接下来讲的是另一种方法——

首先，我们要先求出一个2的幂次方与目标数最接近，之后对他们的差和求出来的指数继续进行如上操作，直到其指数小于等于2。

拿样例来举例：

假如我们要求$137$:

我们找到一个可以被2的幂次方表示出来的，和它最接近的数$127$，也就是$2^7$

而
$$137-127=10$$
$$7=2^2+2^1+2^0$$
$$10=2^3+2^1$$
$$2^3=2^1+2^0$$

所以答案为$137=2(2(2)+2+2(0))+2(2+2(0))+2(0)$

代码

#include <iostream>
#include <algorithm>
using namespace std;

int n;

void work(int num)
{
    cout << "2";
    int i, x = 1;
    for (i = 0; x <= num; i++) //找不大于num最大的数
        x *= 2;
    x /= 2; //多算了一次
    i--;
    if (i > 2) //指数大于2不合法，递归处理
    {
        cout << "(";
        work(i);
        cout << ")";
    }
    else
    {
        if (i == 2 or i == 0)
            cout << "(" << i << ")";
    }
    num -= x;
    if (num) //如果还有剩余，继续处理
    {
        cout << "+";
        work(num);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    if(n == 0)  //0是无解的
        return 0;

    work(n);

    return 0;
}

$$end$$