[Comet OJ - Contest #7] 签到题

签到题(在我看来,是道送命题)

已经提交 已经通过 时间限制: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);
	}

}

 

上一篇:gcd和exgcd和lcm


下一篇:cf55D. Beautiful numbers(数位dp)