题目描述
给定n对正整数ai,bi
,请你求出每对数的最大公约数。
输入格式
第一行包含整数n。
接下来n行,每行包含一个整数对ai,bi
。
输出格式
输出共n行,每行输出一个整数对的最大公约数。
数据范围
1≤n≤105
,
1≤ai,bi≤2∗109
样例
输入样例:
2
3 6
4 6
输出样例:
3
2
算法1
自己做的,但是时间复杂度太高,过不了
Java代码
import java.util.*;
public class Main{
public static void main(String[] ars){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
while(n-->0){
int a=sc.nextInt(),b=sc.nextInt();
int t=a;
while(b%a!=0||t%a!=0){
a--;
}
System.out.println(a);
}
}
}
算法2
老师的公式法
JAVA 代码
import java.util.*;
public class Main{
public static void main(String[] ars){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
while(n-->0){
int a=sc.nextInt(),b=sc.nextInt();
int res=get_divisor(a,b);
System.out.println(res);
}
}
public static int get_divisor(int a,int b){
/*公式法*/
return b!=0?get_divisor(b,a%b):a;
}
}