（取餘運算）快速幂

描述

輸入b，p，k的值，求b^p mod k的值。其中b，p，k×k為長整型數。

格式

輸入格式

輸入b，p，k的值。
           

輸出格式

求b^p mod k的值。
           

樣例

輸入樣例

2 10 9
           

輸出樣例

2^10 mod 9=7
           

限制

時間限制: 1000 ms

記憶體限制: 65536 KB

因為已經習慣用具體題目來講知識，是以本次也不例外，但确實不是一個好的例子來講快速幂，但這道題我一直都是90分，沒有AC，是以拿來講解或許也有一種特殊的意義

代碼如下：

#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <stack>
#include <algorithm>
typedef long long LL;
using namespace std;

LL QuickMi(LL b,LL p,LL k)
{
    LL answer=1;
    while(p>0)
    {

            if(p%2==1)
            {
                answer=(answer*b)%k;
            }
            p/=2;
            b=b*b%k;
    }
    return (answer%k);
}
int main()
{
    LL b,p,k;
    scanf("%lld %lld %lld",&b,&p,&k);
    if(k==0)
    {
        LL answer=0;
        printf("%lld^%lld mod %lld=%lld",b,p,k,answer);
        return 0;
    }
    LL answer=QuickMi(b,p,k);
    printf("%lld^%lld mod %lld=%lld",b,p,k,answer);
    return 0;
}
           

快速幂的關鍵代碼：

LL answer=1;
    while(p>0)
    {

            if(p%2==1)
            {
                answer=(answer*b);
            }
            p/=2;
            b=b*b;
    }
           

快速幂的原理如下：

任何數都可以寫成一下形式：

5=2^2 +2^0

15=2^3 +2^2 +2^1 +2^0

29=2^4 +2^3 +2^2 +2^0

沒錯就是寫成2進制，那麼寫成這樣跟我們快速幂有什麼關系。

因為我們質數n可以寫成n=2^i +2^j+…+ 2^k

• 是以x^n=x ^2 ^i * x^2 ^j *… x^2 ^k

是以這也是b*=b;這裡就是将每個x^i等乘起來。