Things to deal with this problem.
- An infinite Arithmetic progression.
- A prime number. - p.
- The starting number of an Arithmetic Progression. - a.
- Common difference in the arithmetic progression given to him. - d.
You have to print the first index of a number in that Arithmetic Progression, which is a multiple of the given prime number, p.
Input format: The first line contains a number,
tc
, denoting the number of test cases. After that followtc
number of test cases, each is 2 lines - the first contains two integers, a and d - a depicts the first term in the AP, d depicts the common difference. The next line contains the prime number.Output format: You have to print the FIRST index (0-based) of the multiple of the given prime number in the given AP. If no such element exists in this infinite AP, then print -1.
Constraints: 0 <= a, d, <= 10^18 1 <= p <= 10^9
My code:
public static void main(String[] args) throws NumberFormatException, IOException{
StringBuilder output = new StringBuilder();
BufferedReader reader= new BufferedReader(new InputStreamReader(System.in));
int noOfTestCaseT=Integer.parseInt(reader.readLine().trim());
while (noOfTestCaseT != 0){
noOfTestCaseT--;
String[] inputAandD = reader.readLine().split(" ");
long firstElement = Long.parseLong(inputAandD[0].trim());
long commonDifference = Long.parseLong(inputAandD[1].trim());
long primeNo = Long.parseLong(reader.readLine().trim());
firstElement %= primeNo;
commonDifference %= primeNo;
int result = 0;
if(commonDifference == 0) output.append(-1);
else if (firstElement == 0) output.append(0);
else{
long inverseMod = getPowerValue(commonDifference, primeNo);
result = (int) ((inverseMod * (primeNo-firstElement)) % primeNo) ;
output.append(result);
}
output.append("\n");
}
System.out.println(output);
}
private static long getPowerValue(long base, long primeNo) {
long exp = primeNo -2;
long powerResult = 1;
while (exp > 0){
if ((exp & 1) == 1) powerResult = (powerResult * base) % primeNo;
base = (base * base) % primeNo;
exp = exp >> 1 ;
}
return powerResult;
}
How could I can optimize this code further so that its performance improves (though the solution is within the given time limit and I really want to know what are the possible improvement I can make)?