快速幂(Fast Pow)

定义

快速求a^b%c的算法

原理

指数可以被二进制分解

那么a^b可以分解为a^2^k1*a^2^k2*……

又显然a^2^(k+1)=a^(2^k*2)=(a^2^k)^2

所以可以将指数在二进制下从低位向高位递推，每次将底数平方，若该位是1就将答案乘上底数，直到指数为0。

实现时可以每次将指数/2方便处理

位运算优化

x&1：取x二进制下最后一位

x>>1：x/2

代码

int quickpow(int a,int b,const int c)
{
    int base=a%c,ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*base%c;
        base=base*base%c;
        b>>=1;
    }
    return ans;
}

快速幂

例题

一、序列的第k个数

根据元素之差判断是不是等差数列，不是等差数列即为等比数列

推通项公式时注意序列起始为a

#include<cstdio>
#include<cctype>
using namespace std;
#define re register int
#define ll long long
int stk[111],tt;
void print(ll x)
{
    if(x==0)
        putchar('0');
    else
    {
        if(x<0)
            putchar('-'),x=-x;
        tt=0;
        while(x)
        {
            stk[++tt]=x%10;
            x/=10;
        }
        for(re i=tt;i;i--)
            putchar(stk[i]|48);
    }
}
int read()
{
    int x=0,f=0;
    char c=getchar();
    while(!isdigit(c))
    {
        f|=c=='-';
        c=getchar();
    }
    while(isdigit(c))
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return f?-x:x;
}
const int MOD=200907;
ll quickpow(int a,int b,const int c)
{
    ll base=a%c,ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*base%c;
        base=base*base%c;
        b>>=1;
    }
    return ans;
}
int main()
{
    int T=read();
    ll a,b,c,k;
    while(T--)
    {
        a=read(),b=read(),c=read(),k=read();
        if(b-a==c-b)
            print((a+(b-a)*(k-1))%MOD);
        else
            print(a*quickpow(b/a,k-1,MOD)%MOD);
        putchar('
');
    }
    return 0;
}

序列的第k个数

二、[NOIP2013]转圈游戏

走10^k轮即移动m*10^k个位置，再加上x取模即可

#include<cstdio>
#include<cctype>
using namespace std;
#define re register int
#define ll long long
int stk[111],tt;
void print(int x)
{
    if(x==0)
        putchar('0');
    else
    {
        if(x<0)
            putchar('-'),x=-x;
        tt=0;
        while(x)
        {
            stk[++tt]=x%10;
            x/=10;
        }
        for(re i=tt;i;i--)
            putchar(stk[i]|48);
    }
}
int read()
{
    int x=0,f=0;
    char c=getchar();
    while(!isdigit(c))
    {
        f|=c=='-';
        c=getchar();
    }
    while(isdigit(c))
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return f?-x:x;
}
ll quickpow(int a,int b,const int c)
{
    ll base=a%c,ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*base%c;
        base=base*base%c;
        b>>=1;
    }
    return ans;
}
int main()
{
    int n=read(),m=read(),k=read(),x=read();
    ll ans=(x+m*quickpow(10,k,n))%n;
    print(ans);
    putchar('
');
    return 0;
}

转圈游戏

三、[HNOI2008]越狱

可越狱方案数不好求，但从容斥原理的角度，答案可以表示成总排列数-不可越狱排列数

这两个数都很好求，总排列数=m^n，不可越狱排列数考虑第一个数有m种选法，后面每个数都只有m-1种选法，于是=m*(m-1)^(n-1)

#include<cstdio>
#include<cctype>
using namespace std;
#define re register int
#define ll long long
int stk[111],tt;
void print(int x)
{
    if(x==0)
        putchar('0');
    else
    {
        if(x<0)
            putchar('-'),x=-x;
        tt=0;
        while(x)
        {
            stk[++tt]=x%10;
            x/=10;
        }
        for(re i=tt;i;i--)
            putchar(stk[i]|48);
    }
}
ll read()
{
    ll x=0;
    int f=0;
    char c=getchar();
    while(!isdigit(c))
    {
        f|=c=='-';
        c=getchar();
    }
    while(isdigit(c))
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return f?-x:x;
}
const int MOD=100003;
ll quickpow(int a,ll b)
{
    ll base=a%MOD,ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*base%MOD;
        base=base*base%MOD;
        b>>=1;
    }
    return ans;
}
inline int mod(ll a)
{
    a%=MOD;
    if(a<0)
        a+=MOD;
    return a;
}
int main()
{
    ll m=read(),n=read();
    print(mod(quickpow(m,n)-m*quickpow(m-1,n-1)));
    putchar('
');
    return 0;
}

越狱

注意事项

1、根据题目数据范围适当修改快速幂函数中数据的类型

2、取模的数可能<0时注意实际意义