快速幂

作者: endless_e48c | 来源:发表于2020-02-16 13:51 被阅读0次
#include <cstdio>
typedef long long ll;
const int MOD = 100003;
ll n, m;
ll quick_pow(ll a, ll b) {//非递归写法 
    if (b == 0) {
        return 1;
    }
    ll ans = 1;
    while (b > 0) {
        if (b & 1) {
            ans = ans * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}
ll quick_pow1(ll a, ll b) {//递归写法 
    if (b == 0) {
        return 1;
    } 
    ll ans = quick_pow1(a, b / 2) % MOD;
    ans = ans * ans % MOD;
    if (b & 1) {
        return ans * a % MOD;
    } else {
        return ans;
    }
}
int main() {
    scanf("%lld %lld", &m, &n);
    printf("%lld", quick_pow1(m, n)); 
    return 0;
}

相关文章

  • (矩阵)快速幂

    快速乘法: 快速幂: 矩阵快速幂:

  • 快速幂

    常规求幂 快速求幂(一般) 快速求幂 (递归) 快速求幂(位运算) 快速求幂(位运算,更简洁)

  • 快速幂,矩阵快速幂

    快速幂:复杂度为logn,比普通的n快了很多了. 原理 : 实现代码如下:(位运算,简单,简洁) 矩阵快速幂: 所...

  • 模板 | 整数快速幂 & 快速幂取模

    快速幂: 所谓的快速幂,其目的是为了快速求幂,将时间复杂度从朴素算法的降到。 假如现在要求 ,按照朴素算法,就是将...

  • 常用算法

    快速幂 Fast Power 快速取模 FastMode 快速排序 FastSort

  • 2018-07-09-快速幂

    参考:算法学习 - 快速幂和矩阵快速幂(复杂度Olog(n))C++实现 - CSDN博客

  • 快速幂

    对于一个 , 我们可以把它分为 如果化为二进制,则底数为a,指数为0或者1乘以2的次方的权重。我们不妨举例一个例子...

  • 快速幂

    (快速幂)计算A^B的最后x位数 题目描述 请编程计算A^B结果的最后若干位表示的整数. 输入描述 输入数据包含3...

  • 快速幂

    今天的内容是快速幂,是编程中求幂的得力能手,一定要背下来哦。注意:本篇对三目运算符做了一定的介绍。如果已对三目运算...

  • 快速幂

    快速幂用于快速求解a的b次方。将b分解为若干个指数不重复的2的次幂的和,c为0或1。其中时间复杂度

网友评论

      本文标题:快速幂

      本文链接:https://www.haomeiwen.com/subject/wevpfhtx.html