Java实现洛谷 P1072 Hankson 的趣味题

P1072 Hankson 的趣味题

输入输出样例
输入
2
41 1 96 288
95 1 37 1776
输出
6
2

PS：

通过辗转相除法的推导

import java.util.*;class Main{
    public static void main(String args[]){        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), a0, a1, b0, b1, count = 0;        while(n-- > 0){
            a0 = in.nextInt();
            a1 = in.nextInt();
            b0 = in.nextInt();
            b1 = in.nextInt();
            count = 0;
            for(int i = 1; i * i <= b1; i++){
                if(b1 % i == 0){
                    if(cal(i, a0) == a1 && (i / cal(i, b0)) == b1 / b0) count++;
                    if(b1 == i * i) continue;
                    if(cal(b1/i, a0) == a1 && (b0 / cal(b1/i, b0)  == i)) count++;
                }
            }
            System.out.println(count);
        }    }    static int cal(int a, int b){
        if(b == 0)
            return a;
        else
            return cal(b, a % b);
    }}