fzu1752 A^BmodC

rt,很坑很坑的是照着课件打又超时了T^T主要原因： 1<=A,B,C<2^63

肿么办？Tips是说结合快速积求模和快速幂求模

然而还需要再优化~~据说取模这个步骤特别费时间，那就改成减法呗~

思路是什么呢？类似二分的思想，把指数分开算，换言之，就计算A的平方，再平方，再平方，blabla,进行多少次呢？看b能被2除多次啊

就酱紫~~

#include <iostream>
#include<cstdio>
using namespace std;
long long quick(long long a,long long b,long long m)
{
    long long ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a);
        b>>=1;
        a=a*2;
        if(ans>=m) ans-=m;
        if(a>=m) a-=m;
    }
    return ans;
}
int main()
{
    long long a,b,m,t;
    while(~scanf("%I64d%I64d%I64d",&a,&b,&m))
    {
        t=1;
        a=a%m;
        while(b)
        {
            if(b%2) t=quick(t,a,m);
            a=quick(a,a,m);
            b>>=1;
        }
        printf("%I64d\n",t);
    }
    return 0;
}