algorithm - 与求幂相关的任务的更好算法

Question

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

任务包括以下内容:给用户一个数字 N，并且必须计算 a^N (n 的次方，而不是 xor 运算)，我只能通过乘以 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;

可以得到结果。