16级第二周寒假作业H题

快速幂（三）

TimeLimit:2000MS  MemoryLimit:128MB

64-bit integer IO format:%I64d

Problem Description

计算( A^B)%C

 

Input

有多组数据
每组数据有三个整数A,B,C 其中1<=A,B,C<2^63 因为有可能要用到unsigned long long(数值范围 0至2^64-1)

这里提示一下：unsigned long long对应输入输出格式 ：%I64u

数据约2000组

Output

输出(A^B)%C的结果

SampleInput

6 2 8
9 3 7
2 10 23
3 7 57
9223372036854775806 2 9223372036854775807

SampleOutput

4
1
12
21
1

思路：首先做这一题你必须了解快速幂，快速幂我自认为讲的不详细，这里就借鉴了大牛们的一篇帖子，极其详细；http://blog.csdn.net/net_assassin/article/details/38640933
但是你会发现快速幂的话有两个地方碰上大数会直接爆unsigned long long：ans = (ans * a) % c; a = (a * a) % c;就是这两个地方，此时我们发现一个特点，这不就是广义快速幂吗？？
同上，本人语言能力有限，广义快速幂还是要用大牛的文章来介绍：http://www.cnblogs.com/qswg/p/6336508.html
然后有了这两个我们就可以很好的写出代码了。
献上我low逼的代码：
（unsigned long long对应输入输出格式 ：%I64u）

时间：1277MS

长度：275

ll P(ll a, ll b, ll c)
{
    ll r=0;
    a%=c;
    while(b>0)
    {
        if(b&1)
            r=(r+a%c)%c;
        a=(a%c+a%c)%c;
        b>>=1;
    }
    return r;
}

while(b>0)
        {
            if(b%2==1)
            A=P(A, a, c);//将原来是乘法的地方用广义快速幂来解决
            b=b/2;
            a=P(a, a, c);
        }