快速幂（三）

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 89 3 72 10 233 7 579223372036854775806 2 9223372036854775807

SampleOutput

4112211 思路：首先做这一题你必须了解快速幂，快速幂我自认为讲的不详细，这里就借鉴了大牛们的一篇帖子，极其详细； 但是你会发现快速幂的话有两个地方碰上大数会直接爆unsigned long long：ans = (ans * a) % c; a = (a * a) % c;就是这两个地方，此时我们发现一个特点，这不就是广义快速幂吗？？ 同上，本人语言能力有限，广义快速幂还是要用大牛的文章来介绍： 然后有了这两个我们就可以很好的写出代码了。 献上我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);        }