51nod - 1179 - 最大的最大公约数

因为 \(\sum\limits_{i=1}^{n}\lfloor\frac{n}{i}\rfloor=O(nlogn)\)

所以直接暴力就可以了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

int a[50005];

int cnt[1000005]= {};

int main()

{

#ifdef local

    freopen("a.txt","r",stdin);

#endif // local

    scanf("%d",&n);

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

    {

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

        cnt[a[i]]++;

    }

    int maxi=0;

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

    {

        int c=0;

        for(int j=i; j<=1000000; j+=i)

        {

            c+=cnt[j];

            if(c>=2)

                maxi=i;

        }

    }

    printf("%d\n",maxi);

    return 0;

}

还可以记录出现过的最大的a[i]，反向枚举因子，及时退出。

但是没必要。

巴特西

51nod - 1179 - 最大的最大公约数 - 枚举

最新文章

热门文章