数论初步:快速幂

关于幂

所谓幂，就是当计算m个n相乘时，即$n^m$时，n的指数，所谓幂运算就是指针对幂的运算。

求次方

现在给定n和m，请求出$n^m$，那么，首先想到的当然时cmath中提供的pow()函数，既简单又轻便，但是我们知道，这个函数的参数和返回值都是double类型的，精度可能会有误差，或者当需要计算的数很大(通常题目会要求取模一个比较小的数)时（具体之后谈），采用这个直接的方法显然不太过得去，于是我们根据定义自己模拟一下：

查看代码

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\in [1,10^9]$。。。。果断超时，于是想想如何让求幂的运算变快。

对于$10^{8}$而言,是否可以看成是$10^{2^{3}}$，于是我们可以先计算$10^2$，再计算$100^3$这样原来的8次循环减小到了三次，同理$10^{1024}$,此方法将会使循环减小到10次。下面看代码：

查看代码

//还有递归的写法，可以自己实践一下
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\times b)\mod c=(a\mod c \times b\mod c)\mod c$

得到，可以把取模运算分散到计算的每一步中，其次还可以使用位运算来优化，（由计算机组成原理的知识知道直接的位运算要比数学运算来的快），下面给出代码

查看代码

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;
}

快速乘

同样的方法也能将乘法进行这样的变化，俗称快速乘法，不过速度上好像没快多少，但是可以把乘法分解，可以自己动手试试

查看代码

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;
}

参考链接

Ⅰ.境外之主