SSL 2790_次方的运算_数论

发布于 2017-10-25  880 次阅读


题目描述

答案mod 10^9+7


 

思路

显然可得$a^{a^{b-1}}$ 然后将上面的数拆为若干个(p - 1)快速幂即可


#include 
#include 
using namespace std;
#define LL long long
#define p 1000000007
inline LL pw(LL a,LL b)
{
    LL ans = 1;
    a %= p;
    while (b)
    {
        if (b & 1) ans = ans * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return ans;
}
inline LL pw1(LL a,LL b)
{
    LL ans = 1;
    a %= (p - 1);
    while (b)
    {
        if (b & 1) ans = ans * a % (p - 1);
        b >>= 1;
        a = a * a % (p - 1);
    }
    return ans;
}
int main()
{
    LL a, b;
    cin >> a >> b;
    cout << pw(a, pw1(a, b - 1)) << endl;
}

 

]]>