Greatest Greatest Common Divisor

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5207

Description

在数组a中找出两个数ai,aj(i≠j),使得两者的最大公约数取到最大值。

Input

多组测试数据。第一行一个数字T，表示数据组数。对于每组数据，第一行是一个数n，表示数组中元素个数，接下来一行有n个数，a1到an。1≤T≤100,2≤n≤105,1≤ai≤105,n≥104的数据不超过10组。

Output

每组数据输出一行Case #x: ans。x表示组数编号，从1开始。ans表示能取到的最大值。

Sample Input

2
4
1 2 3 4
3
3 6 9

Sample Output

Case #1: 2
Case #2: 3

HINT

题意

题解：

直接枚举每个数的因数

然后倒着枚举，看那个数>=2了，就说明那个数就是最大的gcd;

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 100101

#define mod 10007

#define eps 1e-9

//const int inf=0x7fffffff;   //无限大

const int inf=0x3f3f3f3f;

/*

int buf[10];

inline void write(int i) {

  int p = 0;if(i == 0) p++;

  else while(i) {buf[p++] = i % 10;i /= 10;}

  for(int j = p-1; j >=0; j--) putchar('0' + buf[j]);

  printf("\n");

}

*/

//**************************************************************************************

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int a[maxn];

int cnt[maxn];

int main()

{

    int t=read();

    for(int cas=;cas<=t;cas++)

    {

        memset(a,,sizeof(a));

        memset(cnt,,sizeof(cnt));

        int n=read();

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

        {

            a[i]=read();

            cnt[a[i]]++;

        }

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

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

                cnt[i]+=cnt[j];

        int mx=;

        for(int i=maxn-;i;i--)

            if(cnt[i]>=)

            {

                mx=i;

                break;

            }

        printf("Case #%d: %d\n",cas,mx);

    }

}

秒客网

hdu 5207 Greatest Greatest Common Divisor 数学