快速冪

假設要算311

先把11分解成二進制

11 = 1011(2)

11 = 23×1 + 22×0 + 21×1 +20×1

11 = 8 + 2 + 1

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

3(8+2+1) = 38 × 32 × 31

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

20-> 21-> 22-> 23-> 24

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

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

32 -> 34 = (32)2

所以就可以得到下數列

31 -(平方)-> 32 -(平方)-> 34 -(平方)-> 38 -(平方)-> 316

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

觀察二進制1011

23×1 + 22×0 + 21×1 +20×1

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

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

帶回底數

311 = (32的3次方×1) × (32的2次方×0) × (32的1次方×1) × (32的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讀
求(ab)%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)進去

無理數的快速冪








































#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;
}
Select a repo