Here's the link to the problem
https://cses.fi/problemset/task/1712
And here's my first approach to the problem
#include <bits/stdc++.h>
#define ll unsigned long long
#define nl '\n'
using namespace std;
const ll vpn=1e5+7;
const ll mod=1e9+7;
ll m,n,k,t;
ll a[vpn];
bool iscrit[vpn];
vector<ll> adj[vpn];
ll power(ll a,ll b,ll m)
{
ll r=1;
while (b)
{
if (b&1)
r=r*a%m;
a=a*a%m;
b/=2;
}
return r;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("C://Users/Admin/Desktop/input.txt","r",stdin);
freopen("C://Users/Admin/Desktop/output.txt","w",stdout);
#endif // ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0);
cin>>t;
while(t--)
{
cin>>m>>n>>k;
cout<<power(m,power(n,k,mod),mod)<<nl;
}
}
But I've got all wrong answer, turns out when processing the power(n,k,mod) , it had to be power(n,k,mod-1) . Can someone explain me why do we have to power it and modulo by mod-1?
The reason is behind Fermat’s little Theorem.
It says that if $$$p$$$ is prime and $$$a$$$ is a number such that $$$\gcd(a,p)=1$$$, then $$$a^{p-1} \equiv 1\mod p$$$.
Then, if $$$n=(p-1)\cdot q + r$$$, with $$$r \in [0, p-1)$$$, then $$$a^n = a^{(p-1)q}\cdot a^r \equiv a^r \mod p$$$
As a bonus problem, I suggest the following: you have $$$a,b,c \in [1, 10^6]$$$, you have to compute $$$a!^{b!^{c!}} \mod (10^9+7)$$$.