移动商城型网站开发/企业建站

 P1226 取余运算||快速幂

题目描述

输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。

输入输出格式

输入格式：

 

三个整数b,p,k.

 

输出格式：

 

输出“b^p mod k=s”

s为运算结果

 

输入输出样例

输入样例#1：

2 10 9

输出样例#1：

2^10 mod 9=7

 

　　这是一道很有趣的水题，如果知道公式。

　　一般求解会溢出，导致答案错误。

　　这里介绍取模的一个公式: a*b%k=(a%k)*(b%k)%k.

　　在我们这道题中是b^p = (b^(p/2)%k) * (b^(p/2) %k)%k

　　可以看出来运用的是分治的思维。那么一只分解到p == 1时就能够返回了。

　　蛤？你说p等于奇数时候？ 那就把那个奇数再挑出来呗。 b^p = b * b^(p/2) * b^(p/2)

 

#include <cstdio>

long long b, k;

long long fff(long long p)
{
    if(p == 1)    //p等于1时 b^p%k = b%k;
        return b%k;
    long long temp = fff(p/2); //分~
    temp = (temp*temp)%k;    //注意上面p==1时已经%k,所以这里不需要在括号里面%k
    if(p&1)    //如果p等于奇数
        temp = (temp*b)%k;
    return temp;
}

int main()
{
    long long p;
    scanf("%lld%lld%lld", &b, &p, &k);
    long long ans = fff(p);
    printf("%lld^%lld mod %lld=%lld", b, p, k, ans);
    
    return 0;
}