欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速幂模板(luogu P1226 【模板】快速幂||取余运算)

程序员文章站 2022-05-14 17:17:51
...

题目描述
输入b,p,k的值,求b^p mod k的值。其中b,p,k*k为长整型数。

输入输出格式
输入格式:
三个整数b,p,k.

输出格式:
输出“b^p mod k=s”

s为运算结果

k*k为长整型,所以要想直接for循环你就凉飕飕,高进度写的脑阔又疼,下面就介绍一个神奇的算法,快速幂!!

如210,可以将10分成二进制下的1010,即210=(2(2^1))(2(23))=2228=210;

所以任意一个十进制数都可以转化成二进制数,对于a^b,可以将b拆分为二进制的数并逐步运算,可以在log n 下完成,非常快!!
话不多说,直接上代码。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int a,b,m;
int quickPow(int a,int b,int m){
    int sum=1;
    while(b){
        if(b&1) sum=sum*a%m;
        b>>=1;
        a=a*a%m;
    }
    return sum;
}
int main(){
    scanf("%d%d%d",&a,&b,&m);
    printf("%d\n",quickPow(a,b,m));
    return 0;
}

不理解的地方动手模拟一下代码,应该非常好理解

点个赞啦谢谢!!