Description
给定\(n\)个正整数，求出\(gcd(\{lcm({ai,aj}) | i<j\})\)
Input
第一行一个整数\(n\)
第二行\(n\)个整数
Output
输出答案
Analysis
一条属实有点意思的题目。
结束以后听大佬说是分解定理做，寻思半天没琢磨透，后来还是走的暴力+优化路线。
不妨先看暴力代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100005];
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
int n;
scanf("%d", &n);
int ans = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
for (int j = 0; j < i; j++)
{
int lcm = (a[j] * a[i]) / __gcd(a[j], a[i]);
if (ans == 0)
{
ans = lcm;
}
else
{
ans = __gcd(ans, lcm);
}
}
}
printf("%d", ans);
return 0;
}
算法的复杂度卡在两个for手上，每一次就\(a[i]\)与之前所有数的\(lcm\)时运算过多，考虑优化。可以发现的是\(a[i]\)与之前所有数的\(lcm\)再求\(gcd\)与\(a[i]\)与之前所有数求\(gcd\)再\(lcm\)没有区别
准确的说，对\(a,b,c\)可以证明
$$gcd(lcm(a,c),lcm(b,c))=lcm(gcd(a,b),c)$$
证明较为巧妙，提供如下
需要首先得到引理1
由唯一分解定理可知，任何一个数都可被分解成若干个素数的幂积
我们对一素数\(p\)讨论，有
$$lcm(p^a,p^b)=p^{max(a,b)}$$
$$gcd(p^a,p^b)=p^{min(a,b)}$$
接下来我们需要得到引理2
$$max(min(a,b),c)=min(max(a,c),max(b,c))$$
由对称性不妨假设\(a<=b\)，则\(max(a,c)<=max(b,c)\)易得上结论成立
相信聪明的你已经发现了引理2实质上是对需证明结论对单一素数情况下的特殊情况
我们对一素数\(p\)讨论
原式则有
$$gcd(lcm(p^a,p^c),lcm(p^b,p^c))$$
$$=min(max(p^a,p^c),max(p^b,p^c))$$
$$=max(min(p^a,p^b),c)$$
$$=lcm(gcd(p^a,p^b),p^c)$$
$$Q.E.D$$
于是，我们就可以对求lcm的过程做前缀gcd的优化
即可得解。
Accepted Code
/*
* @Author: Gehrychiang
* @LastEditTime: 2020-05-13 01:29:58
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
* @ProbTitle: (记得补充题目标题)
*/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005];
ll gcdd[100005];
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
int n;
scanf("%d", &n);
ll ans = 0;
for (int i = 0; i < n; i++)
{
scanf("%lld", &a[i]);
if (i == 0)
{
gcdd[0] = a[0];
}
else
{
gcdd[i] = __gcd(gcdd[i - 1], a[i]);
ll lcm = (a[i] / __gcd(a[i], gcdd[i - 1]) * gcdd[i - 1]);
if (ans == 0)
{
ans = lcm;
}
else
{
ans = __gcd(ans, lcm);
}
}
}
printf("%lld", ans);
return 0;
}