Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

One, foreword

Given three positive integers N, M, P, solve for the specific value of NMmodPN^MmodPNMmodP.

The first line is an integer T, representing the amount of test data.

The following T lines each contain three positive integers N,M, and P, 1≤T≤105 1≤N,M,P≤1091≤T≤10^5 1≤N,M,P≤10^91≤T≤105 1≤N,M,P≤109.

Output the result of NMmodPN^MmodPNMmodP.

Powers of numbers.

Two, the title requirements

The sample

Input: 3 2 3 7 4 5 6 5 2 9 Output: 1 4 7Copy the code

inspection

1. Medium type of bit operation, fast power 2Copy the code

Third, problem analysis

16. If you do not know about bit operation, you can read the article in detail.

Day 45: Bit operation.

If you’ve read about bitwise operations, but you haven’t read about fast powers, you should read this

Day 60: Fast powers

And then come back and do this problem and it’s pretty easy.

This problem is a large amount of data, if the ordinary power multiplication modulus operation will surely time out, and with fast power only need to calculate 32 bits can complete the calculation, to be safe we use 64 long long storage.

Four, coding implementation

#include<iostream>
#include<math.h>
using namespace std;
typedef long long ll;// define long long
ll quick_pow(ll n,ll m,ll p)// Fast power template
{
	ll ans=1,base=n;
	while(m! =0)
	{
		if(m&1)
			ans=(ans*base)%p;
		base=(base*base)%p;
		m=m>>1;
	}
	return ans;
}
int main(a)
{
	ll t,n,m,p,i;// Initialize the data
	cin>>t;
	for(i=0; i<t; i++)// loop judgment
	{
		cin>>n>>m>>p;
		cout<<quick_pow(n,m,p)<<"\n";// Output the result
	}
	return 0;
}
Copy the code

V. Test results