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

通过一个模板题简单总结一下快速幂

题目描述

给你三个整数 b,p,k，求b的p次方mod k的值

输入格式

输入只有一行三个整数，分别代表 b,p,k

输出格式

输出一行一个字符串 b^p mod k=s，其中 b, p, kb,p,k 分别为题目给定的值， ss 为运算结果。

输入输出样例

输入 #1复制

2 10 9

输出 #1复制

2^10 mod 9=7

【算法思路】

对于一个数的n次幂，我们可以将它进行拆解，在这里以2^15为例：

step1.答案等于 15 个 2 相乘.
step2.答案等于 7 个 4 相乘再乘上一个 2.
step3.答案等于 3 个 16 相乘再乘上 2*4.
step4.答案等于 1 个 256 乘上 2*4*16.

从以上的步骤中不难看出，当我们求一个数的n次幂的时候，我们可以将它的两两进行配对相乘，如果有多出来的一个数，则将它乘到答案中，否则继续配对，直到只剩下一个数为止。有一个小的注意事项，对答案进行初始化时，初始值应为1而不是0.

【注意事项】

1、每进行一步运算时都要把得到的答案对p取模，否则会只有28分。

2、b m p ans 都要定义成 long long 型变量，不然会只有42分。

3、不要认为运算过程中对答案取模就够了，再输出答案的时候不要忘记把最终的答案再对p取一次模，否则就会只有84分。

4、结合以上几点注意事项的快速幂程序就可以得到100分了。

【代码】

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

int main(){
    long long ans=1,i,j,k,m,n,b,p;
    scanf("%lld%lld%lld",&b,&m,&p);
    printf("%lld^%lld mod %lld=",b,m,p);
    while(m>0){
        if(m%2==1)
            ans=ans*b%p;
        b=b*b%p;
        m=m>>1;
    }
    printf("%lld",ans%p);
    return 0;
}