幂的探究

原文链接我的老博客
【问题】
我们来看到一道题目
求1^m+2^m+……n^m的后k位! (n<=9999 m<=9999 k<=99)
这道题看到的人就会想,快速幂+高精度 直接虐啊!
其实就是这个样子!
但是要加一个优化!
显然我们可以考虑到 对于一个数 p^m 我们可以把其质因数分解然后利用之前的求 p^m
这里不禁要提一下 若p有a,b两个质因子 我们 最后利用 (a*b)^m 这样可以进一步减少高精度乘法的运算次数
【快速幂】
关于快速幂的一个问题
我们都知道快速幂可以说是二分法和倍增法的利用
百度上面都有二分法和倍增法的写法,明显倍增要优越一些!
那是不是我们对幂的加速就已经到头了呢!
其实不然我们来对比一下 快速幂求 4^15 和一种奇怪方法求 4^15 所需乘法的次数
这里我们用p[i]表示 4^i
p[1]=4;
p[2]=p[1]*p[1];
p[4]=p[2]*p[2];
p[8]=p[8]*p[8];
p[15]=p[8]*p[4]*p[2]*p[1];
一共进行了6次乘法运算
这是快速幂的做法!

下面考虑如下奇怪方法
p[1]=i;
p[2]=p[1]*p[1];
p[3]=p[2]*p[1];
p[6]=p[3]*p[3];
p[9]=p[6]*p[3];
p[15]=p[9]*p[6];
仅仅运算了5次乘法运算
【深入思考】
我们情不自禁的发现快速幂所需的乘法次数只是一个比较优秀的!
但并不是最优秀的!经过我的思考和各位大神的帮助我们有如下解法!先且看问题描述!

【问题描述】
求K的n次方,每次相乘的结果可以在后面使用,求至少需要多少次乘。如 2^15
K^1=K*2 1次
K^3=K^2 * 2 2次
K^6=K^3*K^3 3次
K^9=K^6 * K^3 4次
K^15=K^9 * K^6 5次
又如
K^2=K*K
K^4=K^2*K^2
K^5=K^4*K^1
K^10=K^5*K^5
K^20=K^10*K^10
K^40=K^20*K^20
K^80=K^40*K^40
K^120=K^80*K^40
K^125=K^120*K^5
K^127=K^125*K^2
所以 127需要10次

【输入】
一个整数k
【输出】
一个整数 s 表示 计算 n^k最少需要 s次乘法
【题解】
我们考虑一个DFS的算法

用 a[1]~a[k]表示我们已经求出的 p[a[1]]~p[a[k]]
然后我们可以思考剪枝,我们考虑迭代加深
显然a[k]是所得到的幂中最大的一个,假设当前深度下限为d
显然我们p[a[d]]<=p[a[k]]^(d-k) 如果 p[a[k]]^(d-k)<p[n] 显然可以剪枝
这样大体解决问题了!

我们就完成了对幂的探究
【后记】
1.参见2000年论文《信息的充分利用》
2.黑书
3.其实这个东西只是给自己一个思考的空间

Recent Posts

comments powered by Disqus