CODEVS 3500

题目描述

         输入3个数a,b,c，求a^b mod c=?
输入描述
         三个数a,b,c
输出描述
         一个数，即a^b mod c 的答案。
样例输入
5 10 9
样例输出

4

 

基本的二进制快速幂，因为任意一个十进制数可以写成一个二进制权展开式，例如10=2^3+2^1

那么a^10=a^(2^3)*a^(2^1),使用位运算，可以使得代码十分简洁

#include <cstdio>
typedef long long LL;
LL fast_cover(LL a,LL b,LL c)
{
    LL s=1;
    while(b)
    {
        if(b&1) s=(s*a)%c;
        a=(a*a)%c;
        b>>=1;
    }
    return s;
}
int main()
{
    LL a,b,c;
    while(~scanf("%lld%lld%lld",&a,&b,&c))
    {
        printf("%lld\n",fast_cover(a,b,c));
    }
    return 0;
}