BestCoder Round 38-1002 Greatest Greatest Common Divisor

제목 링크:http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=577&pid=1002
제목:
Greatest Greatest Common Divisor  
 Accepts: 271
 
 Submissions: 1138
 Time Limit: 4000/2000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
Problem Description
Pick two numbers  ai,aj(i≠j)  from a sequence to maximize the value of their greatest common divisor.
Input
Multiple test cases. In the first line there is an integer  T , indicating the number of test cases. For each test cases, the first line contains an integer  n , the size of the sequence. Next line contains  n  numbers, from  a1  to  an .  1≤T≤100,2≤n≤105,1≤ai≤105 . The case for  n≥104  is no more than  10 .
Output
For each test case, output one line. The output format is Case # x :  ans ,  x  is the case number, starting from  1 ,  ans  is the maximum value of greatest common divisor.
Sample Input

2
4
1 2 3 4
3
3 6 9

Sample Output

Case #1: 2
Case #2: 3

제목:
    주어진 시퀀스 에서 임의의 두 수의 공약수 의 최대 치 를 구하 십시오.
   hack 때 다른 사람의 코드 를 봤 는데 생각 이 별로 차이 가 없 는 것 같 습 니 다. 대중 해법 인 것 같 습 니 다.
   하나의 수의 인 자 는 그의 제곱 근 까지 만 매 거 할 수 있 고, 다른 한 쪽 은 나 누 면 된다.그리고 각 인자 의 개 수 를 하나의 배열 로 저장 합 니 다.마지막 으로 큰 것 부터 작은 것 까지 어떤 인자 가 2 보다 크 면 바로 답 이다.
코드:

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;
int store[100010],status[100010];
int main()
{
    int n,t,maxx,tmp;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        memset(status,0,sizeof(status));
        scanf("%d",&n);
        for(int j=0;j<n;j++)
        {
           scanf("%d",&store[j]);
        }
            for(int k=0;k<n;k++)
            {
                tmp=store[k];
                for(int x=1;x*x<=tmp;x++)
                {
                    if(tmp%x==0)
                    {
                     status[x]++;
                     status[tmp/x]++;
                    }
                }
            } 
        for(int x=100000;x>=1;x--)
        {
            if(status[x]>=2)
            {
                maxx=x;
                break;
            }
        }
        printf("Case #%d: %d
",i,maxx);
    }
    return 0;
}