Решение задачи Делители двух целых чисел с Codeforces

Без пояснения   Просмотров: 38


Недавно вы получили два положительных целых числа x и y. Вы забыли их, но вы запомнили перемешанный список, содержащий все делители x (включая 1 и x) и все делители y (включая 1 и y). Если d является делителем сразу обоих чисел x и y, то в списке находятся два вхождения d.

Например, если x=4, а y=6, то заданным списком может быть любая перестановка списка [1,2,4,1,2,3,6]. Некоторые примеры возможных списков: [1,1,2,4,6,3,2], [4,6,1,1,2,3,2] или [1,6,3,2,4,1,2].

Ваша задача — восстановить подходящие положительные целые числа x и y, которые формируют заданный список делителей (возможно в другом порядке).

Гарантируется, что ответ существует, то есть заданный список делителей соответствует каким-то положительным целым числам x и y.

Код

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 140;
int a[MAXN];
int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	cout << a[n - 1]<<" ";
	for(int i = n - 2; i >= 0; i--){
		if(a[n - 1] % a[i] != 0 || a[i + 1] == a[i]){
			cout << a[i];
			return 0;
		}
	}
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться