Решение задачи "Фади и НОК" с Codeforces

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


Сегодня Осама вручил Фади целое число X, а Фади стало интересно, какое минимальное значение может принимать max(a,b) таких, что LCM(a,b) равен X. a и b должны быть положительными целыми числами.

LCM(a,b) — это наименьшее положительное целое число, которое делится и на a, и на b. Например, LCM(6,8)=24, LCM(4,12)=12, LCM(2,3)=6.

Разумеется, Фади сразу нашел ответ. Сможете ли вы найти любую такую пару прямо как Фади?

Код

#include<bits/stdc++.h>
using namespace std;
#define int long long int
main()
{
	int n,sym,mx;
	cin>>n;
	for(int i=sqrt(n);i>=1;i--)
	{
		if(n%i==0 && __gcd(i,n/i)==1)
		{
			cout<<i<<" "<<n/i<<endl;
			return 0;
		}
	}
}

         

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


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

Комментарии

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