题目描述

欧几里得算法,也可以叫做辗转相除法

最小公倍数：a * b / gcd(a,b) 如果a和b都是质数，最小公倍数为a * b

样例

//欧几里得算法,也可以叫做辗转相除法
/**  | 这个符号表示整除
 * 基本性质： d|a -> d|b -> d|a+b -> d|ax+by 
 * 核心原理：最大公约数 (a,b) = (b,a%b)  
 * 正证：d|a -> d|b
 * a % b = a - (a / b) * b = a - c * b  由于d|ax+by 所以 d|a-c*b
 * 反证：d|b -> d|a%b
 * a % b = a - (a / b) * b = a - c * b = r
 * 因为 d|b -> d|a - c * b 
 * 由于d|ax+by
 * 则 d|a - c * b + c * b  就等于 d|a ,则反证成功
 **/

import java.util.*;
public class Main{
    public static int gcd(int a,int b){
        return b != 0 ? gcd(b,a % b) : a;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        while(n -- > 0){
            int a = scan.nextInt();
            int b = scan.nextInt();
            System.out.println(gcd(a,b));
        }
    }
}