等等，第二个方法复杂度更高...各位，我错了...

如果对2,3,5做特殊处理，乘法次数还是可以比直接log n少的。

#include <stdio.h>
#include <math.h>
int count;
double mul(double a,double b)
{
    count++;
    return a*b;
}
double Power(double a, int n)
{
    // O(log n)
    double s = 1;

    for (n < 0 && (a = 1. / a, n = -n); n; n >>= 1, a = mul(a,a))
        n & 1 && (s =mul(s, a));

    return s;
}

double FastPower(double a, int n)
{
    int t=2;
    while(n>1) // 应当预先准备素数表，代替t++
    {
        while(n%t==0)
        {
            n/=t;
            switch(t)
            {
                case 2:
                    a=mul(a,a);
                    break;
                case 3:
                    a=mul(mul(a,a),a); // 这里本来应该用临时变量的，利用了一下压栈次序...这么写还是比较危险的- -
                    break;
                case 5:
                    {
                        double t= mul(a,a);
                        a=mul(mul(t,t),a);
                    }
                    break;
                default:
                    a=Power(a, t);
                    break;
            }
            printf("[%d]", t);
        }
        t++;
    }
    return a;
}

int main()
{
    double a;
    int n;
    while(scanf("%lf%d", &a, &n)==2)
    {
        count = 0;
        printf("%lf^%d=\n%lf\n%lf\n", a, n, FastPower(a, n), pow(a, n));
        printf("FastPower count = %d\n", count);
        count = 0;
        printf("%lf^%d=\n%lf\n%lf\n", a, n, Power(a, n), pow(a, n));
        printf("Power count = %d\n", count);
    }
    return 0;
}

可以看到对包含多个小素因数的整数n来说，不做特殊处理的FastPower（也就是直接调用a=Power(a,t)）

究竟如何划分整数n才能更好的减少乘法次数呢？

30 lines to finish this program? You do not know how to program.

接着分析……
P.S. 离比赛结束还有1个小时。

第20楼 chenxun1983
考虑了0的零次方无意义的情况（希望将这个处理放到power函数中~~）。不过没处理负数。

第23楼 catamount3000
修改了在3楼的错误，现在表现良好。

第26楼 littleking
搞不懂你为什么要用指针来做？这是不符合题目要求的。不过测试起来没发现问题。

第27楼 littleking
如果我没看错的话这个和26楼一样吧？不知道怎么回事。

第28楼 Jiff
修改了在10楼的程序，去掉了OodPower函数，效率提高了一些。

第32楼 catamount3000
这个是在搞怪吗？为什么变量名都得搞成o_o，x_x这样？另外说一下，在循环里面写T_T++<((h_h<0)?-h_h:h_h)这种判断条件无论是从可读性还是效率的角度来看，都不是高明的做法。
另外在处理0次方时有错。

第33楼 Jiff
这位仁兄不可谓不努力了。经过多次的改进，终于找到了程序的性能瓶颈。效率有较大提高。这也是本次比赛最开始出现的O(log(n))时间复杂度算法。
啊，那个分是我不小心点上去的~~我用记事本打这段话，切换过去的时候就点到了……

第34楼 euc
虽然都说不参加比赛了，但我还是测试了一下。结果正确，效率比较高。

第36楼 杀死进程
常规的做法，对负数不能正确处理。
另外建议把res=res*a;写为res*=a;

第38楼 lovefreex
算法效率较高，不过有点小毛病。前面写了if(n < 0)n = -n;
后面又写if(n < 0)
        return 1 / (r * b);
    else
        return r * b;
逻辑有点问题，负数将不能返回正确结果。

第39楼 iAkiak
又一个O(log(n))的算法，而且做到了简洁明了，结果与pow函数吻合得很好。很不错！

@sunphy: 你是陕西的sunphy?

比赛结束，锁定此帖。