Codevs 5208 求乘方取模 大数 快速幂取模

新学到的方法    快速幂取模(当数很大时，相乘long long也会超出的解决办法)

---

5208 求乘方取模 

时间限制: 1 s

空间限制: 1000 KB

题目描述 Description

给定非负整数A、B、M，求(A ^ B) mod M。

输入描述 Input Description

包含多组输入，输入处理到EOF。

每组输入仅一行，三个用空格隔开的非负整数A、B、M。

输出描述 Output Description

对于每组输入，输出一行，一个非负整数，即(A ^ B) mod M。

样例输入 Sample Input

2 3 100006

32 71 83

900 800 777

样例输出 Sample Output

8

5

219

数据范围及提示 Data Size & Hint

0 <= A, B < 8 * 10^18。

0 < M < 8 * 10^18。

保证A和B不同时为0。

 

本题仅给出部分关键代码

LL mul(LL a,LL b)

{

    LL ans=0;

    while(b)

    {

        if(b&1) ans=(ans+a)%p;

        a=(a+a)%p;

        b=b>>1;

    }

    return ans;

}

LL Pow(LL a,LL b)

{

    LL result=1;

    LL base=a%p;

    while(b)

    {

        if(b&1) result=mul(result,base)%p;

        base=mul(base,base)%p;

        b=b>>1;

    }

    return result;

}