Programming contests

DEIK Regionális Programozó Csapatverseny, nyílt kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM

gcd

In the interval [A,B] we are searching for a pair of different numbers (x,y) whose greatest common divisor is as large as possible. If the maximum is attained for several pairs, choose the one whose sum is the smallest.

Example

In the figure above we tabulated the greatest common divisors for "pairs between" 10 and 20. It is clear from the table that, on the one hand int the case of A=10,B=20 the maximum is 10 and it only attained at (10,20). On the other hand in the case of A=10,B=14 the maximum is 2 which is attained at several locations: (10,12),(10,14),(12,14). In the latter case we only need (10,12), the one with the smallest sum.

Input Specification

A B

A line with the space separated numbers 1 ≤ A < B ≤ 107 .

Output Specification

x y

A line with space separated values of x < y. Separate them with a space.

Sample Input 1

  1. 10 20
download as text file

Sample Output 1

  1. 10 20
download as text file

Sample Input 2

  1. 11 103
download as text file

Sample Output 2

  1. 51 102
download as text file

Sample Input 3

  1. 1000001 10000000
download as text file

Sample Output 3

  1. 5000000 10000000
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019