First index of number in the arithmetic progression (which is multiple of prime)

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 follow tc 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

Time elapsed is almost all in overhead

I'm not sure you can do any better than what you've done. I tested your program and it ran extremely fast. In fact, I determined that most of the time was probably being spent bringing up the JVM. I ran your program with varying test inputs (up to 100000 test case input), and also ran your program without computing the result (just reading the input and outputting one number per test case). The timings showed that most of the time was being spent just bringing up the JVM (or some other Java related overhead):
100000 test case (times are in seconds)
0.14: bringing up the JVM
0.19: parsing the input and generating output
0.12: calculating the answer
0.45: total time

100 test case
0.14: bringing up the JVM
0.02: parsing the input and generating output
0.01: calculating the answer
0.17: total time


So I believe that your actual algorithm runs for about 0.01 seconds out of 0.17 total time.
C program was faster (less overhead?)

I converted your program to C and tested it to see if it would run any faster. It did run faster, probably because of the lack of overhead:
100000 test case (C program)
0.29: total time

100 test case (C program)
0.01: total time


Here is the C program, just to show you that it is exactly the same as your java program:
#include

static long long getPowerValue(long long base, long long primeNo);

int main(void)
{
int noOfTestCaseT = 0;
long long firstElement, commonDifference, primeNo;

scanf("%d", &noOfTestCaseT);

while (noOfTestCaseT != 0){
noOfTestCaseT--;
scanf("%lld %lld %lld", &firstElement, &commonDifference, &primeNo);
firstElement %= primeNo;
commonDifference %= primeNo;
if(commonDifference == 0) puts("-1\n");
else if (firstElement == 0) puts("0\n");
else {
long long inverseMod = getPowerValue(commonDifference, primeNo);
int result = (int) ((inverseMod * (primeNo-firstElement))%primeNo);
printf("%d\n", result);
}
}
return 0;
}

static long long getPowerValue(long long base, long long primeNo)
{
long long exp = primeNo -2;
long long powerResult = 1;
while (exp > 0){
if ((exp & 1) == 1) powerResult = (powerResult * base) % primeNo;
base = (base * base) % primeNo;
exp = exp >> 1 ;
}
return powerResult;
}

A slightly faster inverse mod function

From wikipedia, I copied this algorithm for finding the inverse mod. Supposedly, it is slightly faster than the algorithm you are using. Using the 100000 test case input, I found that it was a little bit faster, but not by much (maybe 10% faster). Here is the function (it replaces your getPowerValue function):

private static long inverse(long a, long n)
{
    long t    = 0;
    long newt = 1;
    long r    = n;
    long newr = a;

    while (newr != 0) {
        long quotient = r / newr;
        long tmp;

        tmp  = newt;
        newt = t - quotient * newt;
        t    = tmp;

        tmp  = newr;
        newr = r - quotient * newr;
        r    = tmp;
    }
    if (t < 0)
        t += n;
    return t;
}

StackExchange Code Review Q#92919, answer score: 2