签到题(在我看来,是道送命题)
已经提交 已经通过 时间限制:1000ms 内存限制:256MB
82.60%
提交人数:569
通过人数:470
题目描述
多次询问,每次询问给一个值域范围 [l,r][l,r],要回答下列四个问题:
从这个范围内选出两个整数(两个数可相同),
(1) 这两个数的最小公倍数最大是多少?
(2) 这两个数的最小公倍数最小是多少?
(3) 这两个数的最大公约数最大是多少?
(4) 这两个数的最大公约数最小是多少?
输入描述
第一行一个数 tt 表示数据组数 (t = 10^4t=104)。
之后 tt 行,每行两个数 l, rl,r 表示一次询问(1 \le l \le r \le 10^91≤l≤r≤109)。
输出描述
对于每个询问,输出一行四个数依次表示这四个问题的答案。(四个数间恰以一个空白字符隔开,每行行末不能有多余的空白字符。)
样例输入 1
2 2 3 1 2样例输出 1
6 2 3 1 2 1 2 1提示
对于值域范围 [2,3][2,3]:
lcm( 2 , 3 ) = 6lcm(2,3)=6 是最大的最小公倍数
lcm( 2 , 2 ) = 2lcm(2,2)=2 是最小的最小公倍数
gcd( 3 , 3 ) = 3gcd(3,3)=3 是最大的最大公约数
gcd( 2 , 3 ) = 1gcd(2,3)=1 是最小的最大公约数
对于值域范围 [1,2][1,2]:
lcm( 1 , 2 ) = 2lcm(1,2)=2 是最大的最小公倍数
lcm( 1 , 1 ) = 1lcm(1,1)=1 是最小的最小公倍数
gcd( 2 , 2 ) = 2gcd(2,2)=2 是最大的最大公约数
gcd( 1 , 2 ) = 1gcd(1,2)=1 是最小的最大公约数
在这里要注意的是如何求取最大的最小公倍数,最小的最小公倍数,最大的最大公约数,最小的最大公约数;
我在求最小的最大公约数时的思路是先判断在这一范围内有无素数,然后很光荣地牺牲了,复杂度太大,导致超时,然后跟大佬交流之后,发现不用判断有无素数,一个偶数与其相邻奇数之间的最大公约数为1;
大佬说我的复杂度有问题,我要好好看复杂度了,QaQ;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0) {
int l=sc.nextInt();
int r=sc.nextInt();
if(l==r) {
System.out.print(lcm(l,l)+" ");
System.out.print(lcm(l,l)+" ");
System.out.print(gcd(l,l)+" ");
System.out.println(gcd(l,l));
}else {
System.out.print(lcm(r,r-1)+" ");
System.out.print(lcm(l,l)+" ");
System.out.print(gcd(r,r)+" ");
System.out.println(gcd(l,l+1));
}
}
}
private static long lcm(int a, int b) {
// TODO Auto-generated method stub
return a*(b/gcd(a,b));
}
private static long gcd(int a, int b) {
// TODO Auto-generated method stub
return a%b==0?b:gcd(b,a%b);
}
}