# 快速冪

假設要算3^11^

先把11分解成二進制

11 = 1011(2)

11 = 2^3^×1 + 2^2^×0 + 2^1^×1 +2^0^×1

11 = 8 + 2 + 1

所以我們原本要求的3^11^就變成3^(8+2+1)^

3^(8+2+1)^ = 3^8^ × 3^2^ × 3^1^

那藉由二進制的升冪可以發現,每當次方數增加1就會多乘2

2^0^-> 2^1^-> 2^2^-> 2^3^-> 2^4^

1 -> 2 -> 4 -> 8 -> 16

因此,帶回去次方的位置,指數乘2會等於整個數平方

3^2^ -> 3^4^ = (3^2^)^2^

所以就可以得到下數列

3^1^ -(平方)-> 3^2^ -(平方)-> 3^4^ -(平方)-> 3^8^ -(平方)-> 3^16^

#### 結論(1) : 利用自己乘自己得到以二進制為次方的數列

觀察二進制1011

2^3^×1 + 2^2^×0 + 2^1^×1 +2^0^×1

當是0的時候,任何數的0次方都是1,所以可以略過

當是1的時候次方才有意義

帶回底數

3^11^ = (3^2的3次方×1^) × (3^2的2次方×0^) × (3^2的1次方×1^) × (3^2的0次方×1^)

#### 結論(2) : 利用次方的二進制是0或1判斷此數該不該乘到答案裡

int powf(int a,int b){  
    int ans=1;  //答案
    while(b>0){
        if(b%2==1){ //結論(2)
            ans*=a;  //乘到答案裡
        }
        b/=2;  //左移一個
        a*=a;  //結論(1)
    }
    return ans;
}

bitswise + mod 精簡版

#define m 10000007

int powf(int a,int b){
    int ans=1;
    while(b){
        if(b & 1) ans=(ans*a)%m;
        a=(a*a)%m;
        b>>=1;
    }
    return ans;
}

## 大數取模
當指數太大超過long long範圍時,要用string讀
求(a^b^)%m 假設a=123

a=((0*10+1)*10+2)*10+3

取模就是:

a=((((((0*10+1)%m)*10+2)%m)*10+3)%m

int a=0;
for(int i=0;i<str.size();i++){
    a*=10;
    a+=str[i]-'0';
    a%=m;
}

## 無理數快速冪

注意:ans要先放一個(a,b)進去

<a href="https://judge.tcirc.tw/ShowProblem?problemid=d022">無理數的快速冪</a>

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define m 1000000009
using namespace std;

int a,b,n;

pii mul(pii i,pii j){
    pii ans={0,0};
    ans.x+=i.x*j.x;
    ans.y+=i.x*j.y;
    ans.y+=i.y*j.x;
    ans.x+=2*i.y*j.y;
    ans.x%=m;
    ans.y%=m;
    return ans;
}

void solve(){
    pii ans={a,b};
    pii A={a,b};

    n--;
    while(n){
        if(n & 1) ans=mul(ans,A);
        A=mul(A,A);
        n>>=1;
    }
    cout << ans.x << ' ' << ans.y << '\n';
}

signed main(){
    cin >> a >> b >> n;
    solve();
    return 0;
}