题目描述

给你三个整数 b,p,k 求 b^p mod k的值。

输入格式

一行三个整数 b,p,k

输出格式

输出 bp mod k=s

s 为运算结果

输入输出样例

//输入
2 10 9
//输出
7
//2^10 mod 9=7

思路

显然，这道题可以用二分法

即可以将p进行拆解，举个栗子3^90 mod 17

3^90 mod 17= ((3^45 % 17)*(3^45 % 17)) % 17
而3^45 mod 17=((3^22 % 17)*(3^22 % 17)*(3 % 17)) % 17
后3^22 mod 17=((3^11 % 17)*(3^11 %17)) % 17

以此类推得

3^11 % 17 = ((3^5 % 17)*(3^5 %17)*(3 %17)) % 17
3^5 % 17 = ((3^2 % 17)*(3^2 % 17)*(3 % 17)) % 17
3^2 % 17= ((3 % 17)*(3 % 17)) % 17

因此可得如下p的变化

p	p/2
90	45
45	22
22	11
11	5
5	2
2	1

为了提升速度，我们据上表，可知只需计算上表绿色部分，即3^{"绿色部分"} % 17，得代码如下

long long cal(long long b,long long p,long long k) {
    if(p==1) return b%k;
    return ( cal( b , p/2 , k )%k * cal( b , p/2 , k )%k )%k;
}

为了处理当p出现奇数的情况，可在return处添加如下表达式

( p%2==0 ? 1 : b%k )

即当p为偶数时返回1，否则返回b%k

在return处，调用了cal函数两次，不妨优化一下

long long cal(long long b,long long p,long long k) {
    if(p==1) return b%k;
    int t=cal( b , p/2 , k )%k;
    return ( t * t * ( p%2==0 ? 1 : b%k ))%k;
}

输入输出就不必讲了，放代码

# include <iostream>
# include <cstdio>
//# include <stdio.h>
using namespace std;
long long b,p,k;
long long cal(long long b,long long p,long long k) {
    if(p==1) return b%k;
    int t=cal( b , p>>1 , k )%k;//p>>1 即 p/2
    return ( t * t *( p%2==0 ? 1 : b%k ))%k;
}
int main() {
    cin>>b>>p>>k;
//  scanf("%d%d%d",&b,&p,&k);
    printf("%d^%d mod %d=%d",b,p,k,cal( b , p , k ));
    return 0;
}

　　附个洛谷的测试链接P1226 【模板】快速幂||取余运算