分治2--取余運算

分治2--取余運算

一、心得

?

二、題目和分析

?

題目描述

輸入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

提示

解題思路：分治，顧名思義，把一個大問題分解為多個小問題。

　　　這里有一個公式，利用這個公式通過遞歸求得。

?

三、代碼和結果

?

/*
遞推方程
邊界
p==0 1
p/2==0 f(p)=f(p/2)*f(p/2)  
p/2==1 f(p)=f(p/2)*f(p/2)*f(1) 
*/
#include <iostream>
#define ll long long
using namespace std;

ll f(ll b,ll p,ll k){
    if(p==0) return 1;
    else {
        ll tmp=f(b,p/2,k);
        ll ans=((tmp%k)*(tmp%k))%k;
        if(p/2==1) ans=(ans*(b%k))%k;
        return ans;
    }
}

int main(){
    ll b,p,k;
    cin>>b>>p>>k;
    cout<<f(b,p,k)<<endl;
    return 0;
} 

?