数论 快速幂的原理讲解

一. 普通的幂

二. 快速幂

• 模板

三.

　　

(一) 较慢的pow方法 外加 取余。

用到公式:

f(x,y) =   f(x,y/2) * f(x,y/2) * x ( y %2 = 1 and y >=1 )

　　　　1 ( y = 0 )

　　　　f(x,y/2) * f(x,y/2) * x ( y %2 = 0 and y >=1 )

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
    int t;
    int x,y,p;
long long pow(long long x,long long y){
    if(y<=0)
        return 1;
    else if(y%2 == 1)
        return (pow(x,y/2)*pow(x,y/2)*x)%p;
    else if(y%2 == 0)
        return (pow(x,y/2)*pow(x,y/2))%p;
}
typedef long long ll;
ll pow(ll a,ll b){
    ll ans = 1,base = a;
    
}

int main(){

    cin >> t;
    for(int i=0;i<t;++i){
        cin >> x >> y >> p;
    }
    cout << pow(x,y) % p << endl;;
    return 0;
}

 

(二) 那么快速幂是什么? 为什么要用到快速幂？

原因：快

　　普通pow的时间复杂度是 O（n），而快速幂 的时间复杂度为 O（ logn）

假如我们求 X^Y ，

　　当 Y = 8 的时候。

　　X⁸ = X ^{(2^3)}

8的二进制:

　　8₍₂₎ = 1000 = 1 *2^3 + 0 *2^2 + 0 *2^1 + 0 *2^0

那么

　　X^Y = X ^{(2^3)} = X^{(1 *2^3 + 0 *2^2 + 0 *2^1 + 0 *2^0 )}

　　 = 1*  X^{2^3} + 0*  X^{2^2} + 0*  X^{2^1} + 0*  X^{2^0}

　　 = 1*  (((X^{2^0})²)²)²  + 0* ( (X^{2^0})²)² + 0*(X^{2^0})² + 0*  X^{2^0} 

　     = 1*  (((X)²)²)²  + 0* ( (X)²)² + 0*(X)² + 0*  X

 

代码就可以写出。

ll pow(ll x,ll y){
    ll ans = 1,base = x;
    while(y){
        if(y % 2 == 1){
            ans = ans * base;
        }
        base = base * base;
        y/=2;
    }
    return ans;
}

 

用位运算优化一下,

得出模板。

typedef long long ll;
ll pow(ll x,ll y){
    ll ans = 1,base = x;
    while(y){
        if(y&1 != 0){
            ans *= base;
        }
        base *= base;
        y >>= 1;
    }
    return ans;
}

 

如果要加上 取余运算 那么。

typedef long long ll;
ll pow(ll x,ll y){
    ll ans = 1,base = x;
    while(y){
        if(y&1 != 0){
            ans = (ans%p * base%p)%p;
        }
        base = (base%p * base%p) %p;
        y >>= 1;
    }
    return ans;
}

 

题目:

牛客 C-King

链接：https://ac.nowcoder.com/acm/contest/554/C
来源：牛客网

题目描述 
国王有一块神奇土地
第一天可以产a吨粮食，第二天会变成前一天的a倍，以此类推。
n天后大臣准备把这些粮食尽可能多的平均分给b个城池
为了方便，每个城池分到的粮食都是整吨整吨哒！
剩下的粮食国王准备贪污
国王能贪到多少吨粮食呢？

输入描述:
输入的第一行为一个数字T（T<=100），表示数据输入的组数。
之后每行3个数字，分别表示 a, n, b(1<=a,n<= 1000,000,000;1<=b<=1000 )。
输出描述:
对于每组数据输出对应结果
示例1
输入
复制
1
2 2 3
输出
复制
1

代码：

#include <iostream>
using namespace std;
long long pow(long long a,long long b,long long n){
    long long base = a;
    long long ans = 1;
    while(b){
        if(b&1){
            ans = (ans%n * base%n)%n;
        }
        base = (base%n *base%n)%n;
        b>>=1;
    }
    return ans;
}
int main(){
    int T;
    cin >> T;
    long long a,n,b;
    while(T--){
        cin >> a >> n >> b;
        cout << pow(a,n,b) << endl;
    }
    return 0;
}