## L1-111 大幂数

题目链接：https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=1913922872972247046&page=1

**题目分析：这道题还是比较有难度的，比较考察数学基础，但是一般这种数学题给的数据量不会很大，这道题也是，2<n<2^31,所以最大幂肯定不会超过30，**

**题目求的是最大幂次，那我们就可以从30开始计算，这样肯定能找到最大幂，具体看解法代码吧！**

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n;
    cin>>n;
    //这样能保证是最大幂次
    for(int k=30;k>=1;k--){
        ll sum=0;
        ll m=1;
        while (1) {
            // 快速计算 m^k，不循环！
            ll p = 1;
            bool overflow = false;
            for (int i = 0; i < k; ++i) {
                p *= m;
                if (p > n) { // 提前溢出
                    overflow = true;
                    break;//只是跳出了for循环
                }
            }
            if (overflow) break;

            sum += p;
            if (sum == n) {
                // 输出答案
                cout << "1^" << k;
                for (int i = 2; i <= m; ++i) {
                    cout << "+" << i << "^" << k;
                }
                cout << endl;
                return 0;
            }
            if (sum > n) break;

            m++;
        }
    }
    cout<<"Impossible for "<<n<<"."<<endl;
    return 0;
}