I’m trying to implement Fast Exponentiation for this problem
The code i wrote is this:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(final String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
long m=1000000007;
final FastExponentiation exponentiation = new FastExponentiation();
while(t--!=0) {
String line2 = br.readLine();
long a = Long.parseLong(line2.split(" ")[0]);
long b = Long.parseLong(line2.split(" ")[1]);
System.out.println(exponentiation.power(a, b, m));
}
}
}
class FastExponentiation {
public long power(long a, long n, long m) {
if (n == 0) {
return 1;
} else {
long r = power(a, n / 2,m);
if(n%2==0) {
return (r*r)%m;
} else {
return (r*a*r)%m;
}
}
}
}
But i’m not getting the correct result for large values, please help.