专栏首页Don的成长史【蓝桥杯】ADV-204 快速幂

【蓝桥杯】ADV-204 快速幂

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_42449444/article/details/102989593

题目描述:

给定A, B, P,求(A^B) mod P。

输入描述:

输⼊共⼀⾏。 第⼀⾏有三个数,N, M, P。(A, B为long long范围内的⾮负整数,P为int内的⾮负整数)。

输出描述:

一个整数,表示箱子剩余空间。

输入样例:

2 5 3

输出样例:

2

解题思路:

整数快速幂的时间复杂度是

,可以防止TLE,有非递归和递归俩种算法,我是看晴神的《算法笔记》上理解的。

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll quickPow(ll x,ll n,ll m)    //整数快速幂,计算x^n%m
{
    ll ans = 1;
    x %= m;
    while(n)
    {
        if(n&1)   //奇数
        {
            ans = ans*x%m;
        }
        x = x*x%m;
        n >>= 1;
    }
    return ans;
}

ll binaryPow(ll x,ll n,ll m)    //整数快速幂,计算x^n%m递归求解
{
    if(n == 0) return 1;    //若n为0,则x^0=1
    else if(n&2)    //若n为奇数,转换为n-1
    {
        return n*binaryPow(x,n-1,m)%m;
    }
    else    //若n为偶数,转换为n/2
    {
        ll ans = binaryPow(x,n/2,m);
        return ans*ans%m;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ll a,b,m;
    cin >> a >> b >> m;
    cout << quickPow(a,b,m) << endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【蓝桥杯】ALGO-11 瓷砖铺放

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • python爬取bilibili视频

    俺好久没用python的pip了, 今天pip3 install you-get的时候提示我要更新了。

    喜欢ctrl的cxk
  • 【蓝桥杯】2013-A组02 排它平方数

    小明正看着 203879 这个数字发呆。原来,203879 * 203879 = 41566646641。这有什么神奇呢?仔细观察,203879 是个6位数,并...

    喜欢ctrl的cxk
  • 【HDU5778】abs(数学)

    因为每个质因子出现两次,所以y一定可以开根号。于是我们枚举sqrt(x)附近的sqrt(y),质因子都只出现一次就是可行的。比赛的时候我是打好质数表,然后枚举质...

    饶文津
  • 【HDU - 4344】Mark the Rope(大整数分解)

    饶文津
  • 1065. 最小公倍数

    题目描述 输入正整数n,m,编写程序计算n和m的最小公倍数。 输入 一行两个空格隔开的正整数n,m。 输出 输出n和m的最小公倍数。 样例输入 12 18 样例...

    attack
  • Linux Shell(一)——Shell变量

    1 变量的分类 在Linux中,变量分为环境变量 和 局部变量。 环境变量能被子进程继承,而局部变量只能在当前进程中使用。 并且,不论是环境变量还是局...

    大闲人柴毛毛
  • FFmpeg编解码处理3-视频编码

    编码使用avcodec_send_frame()和avcodec_receive_packet()两个函数。

    用户4940323
  • centos6.8下安装部署LNMP-(nginx1.8.0+php5.6.10+mysql5.6.12)

    在平时运维工作中,经常需要用到LNMP应用框架。 以下对LNMP环境部署记录下: 1)前期准备:为了安装顺利,建议先使用yum安装依赖库 [root@opd ~...

    洗尽了浮华
  • 简单入门python字节码混淆

    我就是小菜鸡本鸡了,不是很会写东西,请各位大佬多多见谅。本文基于python2.7,因为python3并不是很懂。

    ChaMd5安全团队

扫码关注云+社区

领取腾讯云代金券