快速幂（三）
TimeLimit:2000MS MemoryLimit:128MB
64-bit integer IO format:%I64d
Problem Description
计算( A)%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)%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=;
a%=c;
while(b>)
{
if(b&)
r=(r+a%c)%c;
a=(a%c+a%c)%c;
b>>=;
}
return r;
}
函数(广义快速幂)
while(b>)
{
if(b%==)
A=P(A, a, c);//将原来是乘法的地方用广义快速幂来解决
b=b/;
a=P(a, a, c);
}
快速幂