C++
We multiply each digit seperately and multiply by the corresponding modular power of 10.
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
using namespace std;
long long int p10[25];
long long int mult(long long int a,long long int b,long long int n){
int ad[13];
int bd[13];
long long int ans=0;
for(int i=0;i<13;i++){//splitting a and b into digits
ad[i]=a%10;
bd[i]=b%10;
b/=10;
a/=10;
}
for(int s=0;s<25;s++){ // s is the sum of the power of 10
int i=s;//Their indexes must add up to s for the order of the place value to be s;
int j=0;
while(i>=0){
if(i<13 && j<13){//They need to be less than 13 otherwise out of bounds
ans+=ad[i]*bd[j]*p10[s]; //multiplying the digits with the corresponding power of 10
ans=ans%n;
}
i--;// going through all possible sums of i&j;
j++;
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >>t;
while(t--){
long long int a,b,n,ans=1;
p10[0]=1;
cin>>a>>b>>n;
for(int i=1;i<25;i++){ // finding powers of 10 modulo n;
p10[i]=p10[i-1]*10;
p10[i]=p10[i]%n;
}
a=a%n;
while(b){ //power still left
if(b%2){ // if its a one in binary form, multiply by this power of a
ans=mult(ans,a,n);
ans=ans%n;
b--;
}
a=mult(a,a,n); //doubling the exponent to the next power of 2
a=a%n;
b/=2;//To go to the next binary digit of b
}
cout<<ans%n<<"\n";
}
}
Python
No explanation needed
for t in range(int(input())):
a,b,n=map(int,input().split())
print(pow(a,b,n))
