CF1349A Orac and LCM 题解

题意分析

给出$n$个数，求这$n$个数两两的最小公倍数的最大公约数

思路分析

通过分析样例可以发现，如果要成为这$n$个数两两的最小公倍数的公约数，至少要是这$n$个数中$n-1$个数的约数，否则就至少会有两个数的最小公倍数无法被这个数整除。

所以只要找出所有满足至少是这$n$个数中的$n-1$个数的约数的数就可以了。找的方法很简单，只要每个数去试一下能整除被几个数就可以了。这里有几个需要注意的点：

- 找出的数应该是质数，否则可能会因为该数的约数已被找出而出错。可以不必先筛出质数，从小到大依次尝试并在找出一个数后除掉它可以保证找出的都是质数。
- 一个数作为约数时次数不一定为1，因此对于一个数要多次尝试
- 尝试的时候如果当前已经有2个数不能被整除，可以直接停止，节省时间

因为最后一点的剪枝，实际上全部尝试的次数很少，因此时间上完全过得去。

#include<iostream>

#include<cstdio>

#define ll long long

using namespace std;

const int N=1e5+100;

int n,maxn;

int a[N];

ll ans=1;

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%d",&a[i]),maxn=max(maxn,a[i]);

    for(int i=2;i<=maxn;i++)

    {

        int cnt=0;

        for(int j=1;j<=n &&(cnt==j-1 || cnt==j-2);j++)

            if(a[j]%i==0)

                cnt++;//尝试能整除几个数

        if(cnt>=n-1)//满足条件

        {

            ans*=i;//累计答案

            for(int j=1;j<=n;j++)

                if(a[j]%i==0)

                    a[j]/=i;//除掉

            i--;//再试一次

        }

    }

    printf("%lld",ans);

    return 0;

}

巴特西

CF1349A Orac and LCM 题解

最新文章

热门文章