题解 CF1349A 【Orac and LCM】

H6_6Q · 2020-05-12 22:47:14 · 题解

题目大意：

给你一个长度为 n 的集合 \{a_1 , a_2\;...\;a_n\}，请你求出 \gcd\{ \text{lcm}(a_i,a_j)\;|\;i < j \}

思路：

众所周知，\text{lcm}(a,b)=\dfrac{a\times b}{\gcd(a,b)}

所以原式可以化为 \gcd\{ \dfrac{a_i\times a_j}{\gcd(a_i,a_j)}\;|\;i < j \}

把 \gcd(a_i,a_j) 提出可得 \dfrac{\gcd\{ a_i\times a_j\;|\;i < j \}}{\gcd(a_1,a_2 \;...\;a_n)}

设我们每次枚举到第 i 个数 a_i 为 x，那么可以将 \gcd\{ x\times a_j\;|\;i < j \} 中的 x 提出，就可以得到 x \times \gcd(a_{i+1},a_{i+2}\;...\;a_{n})。

可以预处理出一个后缀 \gcd ，然后枚举 a_i 计算答案即可。

时间复杂度：常数极小的 \text{O}(n \log a_{max})

记得开 \text{long long} （（

Code：

#include<bits/stdc++.h>
#define LL long long

using namespace std;

LL read()
{
    LL ans=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return ans*f;
}

const LL N=1e5+5;
LL n,a[N],b[N],ans;

int main()
{
    n=read();
    for(LL i=1;i<=n;++i)
        a[i]=read();
    for(LL i=n;i>=1;--i)
    // 预处理后缀 gcd
        b[i]=__gcd(b[i+1],a[i]);
    for(LL i=1;i<=n;++i)
    // 计算 gcd { ai , aj | i < j }
        ans=__gcd(ans,a[i]*b[i+1]);
    // 答案就是 gcd { ai , aj | i < j } / gcd ( a1 , a2 ... an )
    printf("%lld\n",ans/b[1]);
    return 0;
}