I - LCM of GCDshttps://vjudge.csgrandeur.cn/problem/AtCoder-arc124_c思路:
枚举其a[1],和b[1]所有因数。(就是将其归类到红蓝两个袋子里去)然后依次判断一对(a[i],b[i])中是否有两个袋子要的因子。(就是不知道为什么a[1],b[1]的因数是最大公约数)
最后对其求最小公倍数,求最大值。
///苟利国家生死以,岂因祸福避趋之。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 7;
vector<ll> dive(ll x)//求约数
{
vector<ll> res;
for(ll i = 1; i <= x / i; i++)
{
if(x % i == 0)
{
res.push_back(i);
if(x / i != i) res.push_back(x / i);
}
}
return res;
}
ll gcd(ll a, ll b)
{
while(b)
{
ll t = a % b;
a = b;
b = t;
}
return a;
}
ll a[55], b[55];
int main()
{
ll n;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i] >> b[i];
}
vector<ll > A, B;
ll ans = 0, res = 0;
A = dive(a[1]);//换成a[2],b[2]也行,只要任何一对a[i],b[i]都行
B = dive(b[1]);
for(auto x : A)
{
for(auto y : B)
{
bool flag = true;
for(int i = 1; i <= n; i++)
{
if(a[i] % x == 0 && b[i] % y == 0) continue; ///可以分配
if(a[i] % y == 0 && b[i] % x == 0) continue; /// a[i]->y
flag = 0;
break;
}
if(flag)//求最小公倍数
{
ll t = gcd(x, y);
res = x* y/t;
ans = max(ans, res);
}
}
}
cout << ans << endl;
return 0;
}