xuptoj 1476快速幂（演示用）:

所谓的快速幂，实际上是快速幂取模的缩写，简单的说，就是快速的求一个幂式的模(余)。在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法，产生了快速幂取模算法。

1476: 快速幂（演示用）

时间限制: 100 Sec   内存限制: 128 MB
提交: 23   解决: 15
[ 提交][ 状态][ 讨论版]

题目描述

求a的b次方对c取余的结果。

（1<=a,b,c<=1e9）

输入

三个空格隔开的整数a,b,c。

输出

a^b mod c的结果。

样例输入

2 100000000 100000

样例输出

9376

#include<stdio.h>

long long BigMod(long long a,long long b,long long c) {
    if (a == 0 || c == 1)
        return 0;
    if (b == 0)
        return 1;
    if (b % 2)
        return ((a%c)*BigMod(a,b-1,c))%c;
    long long tmp = BigMod(a,b/2,c);
    return (tmp*tmp)%c;
}

int main(void) {
    long long a;
    long long b;
    long long c;
    long long d;
    
    scanf("%lld %lld %lld",&a,&b,&c);
    
    d = BigMod(a,b,c);
    
    printf("%lld\n",d);
    
    return 0;
}