与幂相关的任务的更好算法

Question

最近我在一次比赛中发现了一个有趣的任务，但没有任何作者的解决方案或解释如何解决。

该任务包括以下内容：用户被赋予一个数字 N，并且必须计算 a^N（根据 n 的幂，而不是异或运算），其中我只能通过乘以 a 或之前的结果来计算。我应该给出我应该做的最少数量的计算，以便得到计算a^n。

例：

N=27
Then the answer is 6:
a^2=a*a
a^3=a^2*a
a^6=a^3*a^3
a^9=a^3*a^6
a^18=a^9*a^9
a^27=a^18*a^9

N 的限制如下：N<=40000 。时间和内存限制为：2s and 256MB。

解决此任务的好方法是什么？

提前谢谢你!!

Answer 1

这是一个简单的解决方案，但不够快。我希望有人可以通过一些调整来增强这一点？或者对于只对解决问题感兴趣的人。

#include<set>
#include<iostream>
using namespace std;
int main(int argc, char** argv)
{
    set<int> A, B;
    A.insert(1);
    int n = atoi(argv[1]), i;
    for(i=1; A.find(n) == A.end(); i++) {
        for(auto& a : A) for(auto& b : A) B.insert(a + b);
        for(auto& c : B) A.insert(c);
    }
    cout << i << endl;
}

让我们反过来问..通过计算n次我可以知道多远？它只是每次都翻倍。我错过了什么吗？也就是说，只有这一行，

while(pow(2, n)< atoi(argv[1])) n++;
cout << n;

可以获得结果。