欧拉降幂

问题:如何计算a^(b^c)%p(p是质数)

Tip：排坑,模运算下,加,减,乘,除(乘逆元)时先模p再运算和先运算再模p的结果是一样的,但是对于幂运算就失效了,可以自己试试.
那如何解决这个问题呢
我们知道费马小定理:设a,p互质,则有a^(p-1)%p=1.
对于我们要求的式子:令b^c=t,再将t写成k*(p-1)+r。
那原式就变成了a ^ ( k * ( p - 1 ) + r ) % p = (a ^ ( k * ( p - 1 ) )) %p *( a ^ r ) % p.
由费马小定理可知a^(k*(p-1))%p=1,所以原式=a^r%p.
到了这里会有疑问,r是什么呢？
上面的t=k*(p-1)+r,很显然,r=t%(p-1),到此为止问题就解决了:
1.先计算b^c%(p-1),假设=x.
2.计算a^x%p.
到头来就是两次快速幂.
下面是代码：

int qmi(int a,int b,int p)//计算a^b%p
{
    int res=0;
    while(b)
    {
        if(b&1)res=(long long)res*a%p;
        a=(long long)a*a%p;
        b>>=1;
    }
    return res;
}
int get_(int a,int b,int c,int p)//计算a^(b^c)%p
{
    int x=qmi(b,c,p-1);
    return qmi(a,x,p);
}

欢迎指正