关于幂
所谓幂，就是当计算m个n相乘时，即nm时，n的指数，所谓幂运算就是指针对幂的运算。
求次方
现在给定n和m，请求出nm，那么，首先想到的当然时cmath中提供的pow()函数，既简单又轻便，但是我们知道，这个函数的参数和返回值都是double类型的，精度可能会有误差，或者当需要计算的数很大(通常题目会要求取模一个比较小的数)时（具体之后谈），采用这个直接的方法显然不太过得去，于是我们根据定义自己模拟一下：
查看代码
1
2
3
4
5
6
7
8
| typedef long long ll;
ll myPow(ll x, ll y){
ll ans = 1;
for(int i = 0; i < y; i++){
ans *= x;
}
return ans
}
|
优化
如果题目要求m∈[1,109]。。。。果断超时，于是想想如何让求幂的运算变快。
对于108而言,是否可以看成是1023，于是我们可以先计算102，再计算1003这样原来的8次循环减小到了三次，同理101024,此方法将会使循环减小到10次。下面看代码：
查看代码
1
2
3
4
5
6
7
8
9
10
11
|
typedef long long ll;
ll myPow(ll x, ll y){
ll ans = 1;
while(y != 0){
if(y%2) ans *= x;
x *= x;
y /= 2;
}
return ans;
}
|
如果所求数很大，一般会让取模，由模运算的规则：
(a×b)modc=(amodc×bmodc)modc
得到，可以把取模运算分散到计算的每一步中，其次还可以使用位运算来优化，（由计算机组成原理的知识知道直接的位运算要比数学运算来的快），下面给出代码
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| const int mod=10;
typedef long long ll;
ll quickPow(ll x,ll y)
{
ll ans=1;
while(y&1)
{
if(y%2)
ans=(ans*x)%mod;
x=(x*x)%mod;
y>>=2;
}
return ans;
}
|
快速乘
同样的方法也能将乘法进行这样的变化，俗称快速乘法，不过速度上好像没快多少，但是可以把乘法分解，可以自己动手试试
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| const int mod=10;
typedef long long ll;
ll qt(ll x,ll y)
{
ll ans=0;
while(y&1)
{
if(y%2)
ans=(ans+x)%mod;
x=(x+x)%mod;
y>>=2;
}
return ans;
}
|
参考链接
Ⅰ.境外之主
