Orac and LCM
题意
有一个数组s,相关定义如下
- \(gcd(s)\)是最大的一个整数x,s中的所有数字都可以整除x
- \(lcm(s)\)是最小的一个整数x,x可以整除s中的所有数字
给出一个有n个数字的数组a,根据数组a,得到另一个数组\(t=\{lcm(a_i,a_j)|i<j\}\),
让求出\(gcd(t)\)
思路
\[\begin{aligned} gcd(t)=&gcd\{\\ &gcd\{lcm(a_1,a_2),lcm(a_1,a_3),lcm(a_1,a_4)...lcm(a_1,a_n)\},\\ &gcd\{lcm(a_2,a_3),lcm(a_2,a_4)...lcm(a_2,a_n)\},\\ &...\\ &gcd\{lcm(a_{n-2},a_{n-1}),lcm(a_{n-2},a_n)\},\\ &gcd\{lcm(a_{n-1},a_n)\}\\ \} \end{aligned} \]
单看\(gcd\{lcm(a_1,a_2),lcm(a_1,a_3),lcm(a_1,a_4)...lcm(a_1,a_n)\}\)
可以知道\(lcm(a,b)=a*\frac{b}{gcd(a,b)}\),那么
\[\begin{aligned} &gcd\{lcm(a_1,a_2),lcm(a_1,a_3),lcm(a_1,a_4)...lcm(a_1,a_n)\}\\ &=gcd\{a_1*\frac{a_2}{gcd(a_1,a_2)},a_1*\frac{a_3}{gcd(a_1,a_3)},a_1*\frac{a_4}{gcd(a_1,a_4)}...a_1*\frac{a_n}{gcd(a_1,a_n)}\}\\ &=a_1*gcd\{\frac{a_2}{gcd(a_1,a_2)},\frac{a_3}{gcd(a_1,a_3)},\frac{a_4}{gcd(a_1,a_4)},...,\frac{a_n}{gcd(a_1,a_m)}\}\\ &=a_1*\{\frac{gcd\{a_2,a_3,a_4,..,a_n\}}{gcd\{a_1,gcd\{a_2,a_3,a_4,..,a_n\}\}}\}\\ &=a_1*\{\frac{gcd\{a_2,a_3,a_4,..,a_n\}} {gcd\{a_1,a_2,a_3,a_4,..,a_n\}}\}\\ \end{aligned} \]
定义\(suf[i]=gcd\{a_i,a_{i+1},a_{i+2},...,a_{n-1},a_n\}\),那么
\[\begin{aligned} gcd(t)=gcd\{\\ &a_1*\frac{suf[2]} {suf[1]},\\ &a_2*\frac{suf[3]} {suf[2]},\\ &...\\ &a_{n-2}*\frac{suf[n-1]} {suf[n-2]},\\ &a_{n-1}*\frac{suf[n]} {suf[n-1]},\\ \} \end{aligned} \]
最后顺序求一遍\(a_i*\frac{suf[i+1]}{suf[i]}\)的gcd就可以了
代码
/*Gts2m ranks first in the world*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
ll suf[N],arr[N],rel[N];
int main()
{
ll n;
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&arr[i]);
suf[n+1]=arr[n];
for(ll i=n;i;i--)
{
suf[i]=__gcd(suf[i+1],arr[i]);
rel[i]=1LL*suf[i+1]/suf[i]*arr[i];
}
ll ans=rel[n-1];
for(ll i=1;i<n-1;i++) ans=__gcd(ans,rel[i]);
printf("%lld\n",ans);
return 0;
}