HDOJ(HDU) 2504 又见GCD(利用最大公约数反推)

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);

        int t =sc.nextInt();
        while(t-->0){
            int a =sc.nextInt();
            int b =sc.nextInt();
            int c=0;
            for(int i=2;;i++){
                if(goc(a,i*b,b)){
                    c=i*b;
                    break;
                }
            }
            System.out.println(c);
        }
    }

    //验证，a和c的最大公约数是不是b
    private static boolean goc(int a, int c, int b) {
        int n=a;
        int m=c;
        if(n<m){
            n=n^m;
            m=n^m;
            n=n^m;
        }

        while(m>0){
            int k=n%m;
            n=m;
            m=k;
        }
        if(n==b){
            return true;
        }
        return false;
    }
}