---
title : 題解：快速冪(上)
tags : solution
---

# 快速冪計算流程

稍微展示一下，快速冪的運作流程：`ex` $7^{26}$

| 次方數二進位 | 當前位元狀態 | 當前倍數 | 計算後答案 |
| - | - | - | - |
| <font color=blue>11010</font> | | | $1$ |
| <font color=blue>1101</font><font color=red>0</font> | <font color=red>0</font> | $7^1$ | $1$ |
| <font color=blue>110</font><font color=red>1</font><font color=gray>0</font> | <font color=red>1</font> | $7^2$ | $1×$<font color=red>$7^2$</font> |
| <font color=blue>11</font><font color=red>0</font><font color=gray>10</font> | <font color=red>0</font> | $7^4$ | $1×$$7^2$ |
| <font color=blue>1</font><font color=red>1</font><font color=gray>010</font> | <font color=red>1</font> | $7^8$ | $1×$$7^2×$<font color=red>$7^8$</font> |
| <font color=red>1</font><font color=gray>1010</font> | <font color=red>1</font> | $7^{16}$ | $1×$$7^2×$$7^8×$<font color=red>$7^{16}$</font> |
| <font color=gray>11010</font> | | | $1×$$7^2×$$7^8×$$7^{16}=7^{26}$ |

快速冪有個「>>=」的處理，這就是在跑「移動紅色位置」的部分，
(作用在於判斷最右邊位元數( if n&1 )後，將整個二進位都往右推一位)
而 x*=x 的處理，用途在於將「次方數值往左推一位」，
亦可以看成是：( $7^1,7^2,7^4,7^8,7^{16}$ ) $·$ ( $0,1,0,1,1$ )，把內積運算過程的加號改成乘號之計算結果
(原本的二進位是 ( $1,2,4,8,16$ ) $·$ ( $0,1,0,1,1$ ) 的內積運算結果)

---

# 從二進位到快速冪(程式碼比較)

計算二進位為1的數量：

int bit_amount(int n){
    int r = 0;
    
    while(n){
        if(n&1)
            r++;
        n>>=1;
    }
    
    return r;
}

次方快速冪，多了需要處理倍數的部分：

int pow(int x, int n){
    int r = 1;
    
    while(n){
        if(n&1)
            r*=x;
        x*=x;
        n>>=1;
    }
    
    return r;
}

次方快速冪，多了處理模運算的部分：

int pow(int x, int n, int MOD){
    int r = 1;
    
    while(n){
        if(n&1){
            r*=x;
            r%=MOD
        }
        x*=x;
        x%=MOD
        n>>=1;
    }
    
    return r;
}

---

# ZJ d636 - 大爆炸
- [d636 - 大爆炸](https://zerojudge.tw/ShowProblem?problemid=d636)

典型的次方快速冪題目。

# include <stdio.h>

#define MOD 10007

int main(){

    int a,n ,r = 1;
    scanf("%d%d",&a,&n);
    do{
        if(n&1){
            r*=a;
            r%=MOD;
        }
        a*=a;
        a%=MOD;
    }while(n>>=1);

    printf("%d",r);
}

>執行結果：
> Time : 1 ms
> Memory : 84 KB

---
# UVa 374 - Big Mod
- [374 - Big Mod](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=310)

與上一題幾乎相同，只不過型態要記得開大一點
(如果把 $2^{31}-1$ 平方，就會超出int值域，使答案溢位(overflow) )。

# include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    long long int a,n,mod,r;
    while(cin>>a>>n>>mod){
        r = 1;
        while(n){
            if(n&1){
                r*=a;
                r%=mod;
            }
            a*=a;
            a%=mod;
            n>>=1LL;
        }
        cout<<r<<'\n';
    }
}

>執行結果：
> Time : 0 ms

---
# POJ 1995 - Raising Modulo Numbers
- [1995 - Raising Modulo Numbers](http://poj.org/problem?id=1995)

通常會把快速冪寫成函式(pow)，最主要原因還是因為邏輯方便(#

# include <stdio.h>

typedef long long ll;

ll pow(ll a, ll b, const int &M){
    ll r = 1;

    do{
        if(b&1){
            r*=a;
            r%=M;
        }
        a*=a;
        a%=M;
    }while(b>>=1);
    
    return r;
}

int main(){
    int Z,M,H;
    ll a,b,sum;
    
    scanf("%d",&Z);
    while(Z--){
        scanf("%d%d",&M,&H);
        sum = 0;
        
        while(H--){
            scanf("%lld%lld",&a,&b);
            sum += pow(a,b,M);
            sum %= M;
        }
        
        printf("%lld\n",sum);
    }
}

> 執行結果：
> Time : 125 ms
> Memory : 88 KB

---
# LeetCode 50 - Pow(x,n)
- [50 - Pow(x,n)](https://leetcode.com/problems/powx-n/)

僅只是把整數底換成小數底，並且要考慮負數次方的快速冪問題
(甚至還不需要考慮模算數)
(註：矩陣快速冪，就是把底換成「矩陣」，以此類推)

double myPow(double x, long long n) {
    double r = 1;
    if(n<0)
        x = 1/x, n = -n;

    do{
        if(n&1)
            r*=x;
        x*=x;
    }while(n>>=1);

    return r;
}

> 執行結果：
> Time : 0 ms (Rated 100%)
> Memory : 5.9 MB (Rated 86.08%)

###### posted date: `2021.3.7`