快速冪

數字太大要求mod的題目會需要在過程中mod
所以有時候必須自己寫

一、基本寫法

#include <bits/stdc++.h>
using namespace std;

int po(int x,int y){
    if(y==0){
        return 1;
    }
    if(y&1){
        return po(x,y-1)*x;//奇數冪次
    }
    else{
        int x=po(x,y/2);//避免運算兩次
        return x*x;//偶數冪次
    }
}

int main(){
    //2的10次方(1024)
    cout<<po(2,10);
}

二、迴圈寫法

每次遞迴調用都需要額外的開銷，包括函數調用和返回地址的保存。這些開銷在迴圈版本中是不存在的。使用迴圈比較快。

講解：

以 \(2^{10}\) 為例，\(10\) 二進制為 \(1010\)

1	0	1	0
8	4	2	1
\(2^8\)	\(2^4\)	\(2^2\)	\(2^1\)

由表個中可以知道\(10=8+2\)
若\(10\)在指數為 \(a^{10}\) ， 那 \(a^8 *a^2 = a^{2+8}=a^{10}\)

所以我們只要製作出一個圈可以跑\(2^8 , 2^4 ,2^2 , 2^1\)

接著用位元運算，當位置為 \(1\) 時，就乘上對應的數字。

跑\(2^8 , 2^4 ,2^2 , 2^1\)程式：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,x=2;
    cin>>n;
    for(int i=0;i<n;i++){
        cout<<x<<" ";
        x*=x;
    }
}

putput

2 4 16 256 

接下來使用位元運算對應需要相乘的數字：

int po(int x, int y) {
    int ans = 1;//都沒有乘的話為1
    while (y > 0) {
        if (y & 1) {
            ans *= x;//需要乘上去
        }

        x = (x * x);//跑2 4 16 256...
        y >>=1;//右移，將1010變成101
    }
    return ans;
}

最後就可以使用此方法作為快速幂迴圈方法

完整代碼

#include <bits/stdc++.h>
using namespace std;

int po(int x, int y) {
    int ans = 1;
    while (y > 0) {
        if (y & 1) {
            ans *= x;
        }
        x *= x;
        y >>=1 ;
    }
    return ans;
}
int main(){
    //2的10次方(1024)
    cout<<po(2,10);
}

1024

求mod寫法(根據模運算性質)

P-2-3. 快速冪

題目：https://judge.tcirc.tw/ShowProblem?problemid=d012

輸入正整數 x, y, 與 p，計算 x
y (mod p)。x, y, p 皆不超過 1e9+9。例如 x=2,
y=5, p=11，則答案是 10。
Time limit: 1 秒
輸入格式：輸入 x, y, 與 p 在同一行，以空白間隔。
輸出格式：輸出計算結果。
範例輸入：
2 5 11
範例輸出：
10

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL po(LL x,LL y,LL z){
    if(y==0){
        return 1;
    }
    if(y&1){
        return po(x,y-1,z)*x%z;
    }
    else{
        LL t=po(x,y/2,z);
        return (t%z)*(t%z);
    }
}

int main(){
    LL x,y,z;
    cin>>x>>y>>z;
    cout<<po(x,y,z);
}

Q-2-4. 快速冪–200 位整數

題目：https://judge.tcirc.tw/ShowProblem?problemid=d013

題目與輸入皆同於 P-2-3，但 x 的範圍是不超過 200 位的正整數
範例輸入： 123456789012345678901234567890 5 11
範例輸出： 10

我們可以在字串轉數字時順便mod(根據模運算性質
原本轉字串寫法如下：

字串寫法

//製作取餘數後的字串
LL mack(string s,LL z){
    LL ans=0;
    LL ssize=s.size();
    for(LL i=0;i<ssize;i++){
        ans*=10;
        ans%=z;
        ans+=s[i]-'0';
    }
    return ans%z;
}

解答

#include <bits/stdc++.h>
using namespace std;
#define nn "\n";
typedef long long LL;

//製作取餘數後的字串
LL mack(string s,LL z){
    LL ans=0;
    LL ssize=s.size();
    for(LL i=0;i<ssize;i++){
        ans*=10;
        ans%=z;
        ans+=s[i]-'0';
    }
    return ans%z;
}


LL po(LL x,LL y,LL z){
    if(y==0){
        return 1;
    }
    if(y&1){
        return po(x,y-1,z)*x%z;
    }
    else{
        return po(x,y/2,z)*po(x,y/2,z)%z;
    }
}

int main(){
    LL x,y,z;
    string s;
    cin>>s;
    cin>>y>>z;
    x=mack(s,z);
    cout<<po(x,y,z);
}

expandcollapse