CODEVS 3500

题目描述

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

基本的二进制快速幂，因为任意一个十进制数可以写成一个二进制权展开式，例如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=;

    while(b)

    {

        if(b&) s=(s*a)%c;

        a=(a*a)%c;

        b>>=;

    }

    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 ;

}

巴特西

CODEVS 3500

最新文章

热门文章