GCD and LCM FLOW016

Please someone tell me whats wrong in the following code. It works for the test case given in the question but still on submitting it gives wrong answer.

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner input = new Scanner(System.in);
int t = input.nextInt();
for(int i = 0; i < t; i++){

		int a = input.nextInt();
		int b = input.nextInt();
		int dividend = a > b ? a : b;
		int div = a < b ? a : b;
		int rem = dividend % div;
		
		while(rem != 0){
		    
		    dividend = div;
		    div = rem;
		    rem = dividend % div;
		}
		System.out.println(div + " " + ((a * b) / div));
	}
	
}

}

Consider the test input:

1
1000000 999999
1 Like

do (a*(b/div)) instead to avoid int overflow(see constraints)