#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int power(long long a, int b)
{
long long res = 1;
if (!b) return res;
a %= mod;
if (!a) return 0;
while (b > 0)
{
if (b & 1) res = ((res*a)%mod);
b >>= 1;
a = ((a*a)%mod);
}
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
cin >> n;
while (n--)
{
long long a, b, c;
cin >> a >> b >> c;
cout << power(a, power(b, c)) << '\n';
}
}
We have to find a^{b^c} \pmod{10^9+7}, \ 0 \leq a, \ b, \ c \leq 10^9 which I do in O(\log{b} + \log{c}) with modular exponentiation. For some reason, it shows WA.
For example,
case: 3 9 10
expected: 112070339
output: 967113723
Also, assume that 0^0 = 1.
I don’t know what I’ve done wrong because it passes most cases.
Please help me.
pow(a,totient(mod)) == 1 (mod) // Fermat’s theorem
Since mod here is prime
Therefore , pow(a,mod-1) == 1 (mod)
So basically taking pow(b,c)%(mod-1) will eliminate all 1’s.
And suppose x = pow(b,c)%(mod-1)
Then answer is simply pow(a,x)%mod
Firstly, you need to calculate a^{(b^c)} \mod p. You can calculate x = b^c \mod \phi(p), and then calculate a^x \mod p. This is because we know a^{\phi(p)} \equiv 1 \mod p if \gcd(a,p) = 1.
Also it’s not O(\log b \log c) it’s O(\log b + \log c)
If I want to calculate a^(b^(c^(d))) mod p and regarding ‘p’ I don’t know whether it is prime or not, then how to solve this problem.
Thanks in advance.