快速幂取模算法

2017-12-08 本文已影响1041人 SpiffyEight77

Cover.jpg

前言

在算法程序设计竞赛中，我们竞赛选手会经常碰到对某个数N进行求大数次幂并对1e9+7取模的运算的题目，一方面求大数次幂是一个时间复杂度很高的运算（容易超时），另一方面对1e9+7取模，暗示着结果是连long long都存不下（同余定理），所以这时候快速幂取模算法就派上用场了。

同余定理

首先介绍一下同余定理，公式如下👇（不推导了！大家可以自行代数进去验证）

(a +/- b) % c = (a % c +/- b % c) % c

(a * b) % c = (a % c) * (b % c) % c

a^b % c = (a % c)^b % c

快速幂取模

现在来讲讲快速幂的原理，首先假设我们有 a^b % c （1 <= a , b <= 1e5 c = 1e9+7）这样一个式子，要求出它的结果，上面已经讲过正常思路的做法肯定是会超时或者结果溢出的，所以我们可以把式子展开：

把b转换成由01组成的二进制串 b = b₀ * 2⁰ + b₁ * 2¹ + b₂ * 2² + b₃ * 2³ + ...... + b_n * 2ⁿ

那么 a^b = a^{b₀ * 2⁰} * a^{b₁ * 2¹} * a^{b₂ * 2²} * a^{b₃ * 2³} * ...... * a^{b_n * 2ⁿ}

根据同余定理可得 a^b % c = (a^{b₀ * 2⁰} % c) * （a^{b₁ * 2¹} % c) * (a^{b₂ * 2²} % c) * (a^{b₃ * 2³} % c) * ...... * a^{b_n * 2ⁿ} % c) % c

最后去掉b_i = 0 的项（等于1） a^b % c = (a^{b_i * 2ⁱ} % c) * （a^{b_i+1 * 2ⁱ⁺¹} % c) * (a^{b_i+4 * 2ⁱ⁺⁴} % c) * ...... * a^{b_n * 2ⁿ} % c) % c

我们用例子再来解释快速幂原理，已知2¹⁰ = 1024 10₍₁₀₎ = 1010₍₂₎

2¹⁰ = 2^{0 * 2⁰ + 1 * 2¹ + 0 * 2² + 1 * 2³}

2¹⁰ = 2^{0 * 2⁰} * 2^{1 * 2¹} * 2^{0 * 2²} * 2^{1 * 2³}

2¹⁰ = 1 * 2^{1 * 2¹} * 1 * 2^{1 * 2³}

2¹⁰ = 1 * 2² * 1 * 2⁸

观察第二条推导式可知从左往右第二项数起每一项的指数都是前一项的平方倍，所以在用代码实现的时候，我们对指数（二进制）按位平方略过为指数为0的项，大大降低了时间复杂度（0较多的前提下）。

C++代码实现快速幂取模

long long quick_mod(long long a,long long b)
{
    long long ans = 1;
    a %= Mod; //对刚进来的a进行取模运算，避免后面第一次求平方运算溢出
    while(b)
    {
        if(b&1) //对二进制下的 b 进行按位与1运算，求二进制下 b 的最低位是否为1
            ans = ans * a % Mod; //对结果进行保存
        b>>=1; //二进制下的 b 右移一位，相当于十进制下的 b 除以2
        a = a * a % Mod; 
    }
    return ans % Mod;
}

POJ - 1995 Raising Modulo Numbers

快速幂取模（模板题），给出Z大块，和M（需要取模的数），让你求n对x^y的和对M取模的结果。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll t,n,x,y,res,ans,Mod;
ll quick_mod(ll a,ll b)
{
    ans = 1;
    while(b)
    {
        if(b&1)
            ans = ans * a % Mod;
        b>>=1;
        a = a * a % Mod;
    }
    return ans % Mod;
}
int main()
{
    cin>>t;
    while(t--)
    {
        res = 0;
        cin>>Mod;
        cin>>n;
        for (int i = 0; i < n; i++)
        {
            cin>>x>>y;
            res = (res + quick_mod(x,y)) % Mod;
        }
        cout<<res%Mod<<endl;
    }
    return 0;
}

HDU - 3003 Pupu

pupu是一种特殊的生物，它有n层皮肤，皮肤有透明和不透明两种状态，其中pupu出生时候所有皮肤都不透明，皮肤只要被晒一天，到第二天就会切换到另一种状态，而pupu需要每层皮肤都从不透明转换到透明一次才能成为成年pupu，问需要多少天？

0表示不透明1表示透明
N = 2 00 --> 10 --> 01 3天
N = 3 000 --> 100 --> 010 --> 110 --> 001 5天
根据上面可以推导出公式
Day % n = ( 2^n-1 + 1) % n

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll n,a,ans,k,Mod;
ll quick_mod(ll k)
{
    ans = 1;
    a = 2;
    while(k)
    {
        if(k&1)
            ans = ans * a % Mod;
        k>>=1;
        a = a * a % Mod;
    }
    return ans % Mod;
}
int main()
{
    while(scanf("%lld",&n) && n)
    {
        Mod = n;
        cout<<(quick_mod(n-1) + 1) % Mod<<endl;
    }
    return 0;
}