AtCoder Beginner Contest 182B

B - Almost GCD

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 200 points

Problem Statement

Given is an integer sequence A: A1,A2,A3,…,AN.Let the GCD-ness of a positive integer k be the number of elements among A1,A2,A3,…,AN that are divisible by k.Among the integers greater than or equal to 2, find the integer with the greatest GCD-ness. If there are multiple such integers, you may print any of them.

Constraints

• 1≤N≤100≤N≤100
• 2≤Ai≤1000
• All values in input are integers.

Input

Input is given from Standard Input in the following format: N A1A2A3…AN

Output

Print an integer with the greatest GCD-ness among the integers greater than or equal to 22. If there are multiple such integers, any of them will be accepted.

Sample Input 1 

3 3 12 7

Sample Output 1 

3

Among 3, 12, and 7, two of them - 3 and 12 - are divisible by 3, so the GCD-ness of 3 is 2.

No integer greater than or equal to 2 has greater GCD-ness, so 3 is a correct answer.

Sample Input 2 

5 8 9 18 90 72

Sample Output 2 

9

In this case, the GCD-ness of 9 is 4

2 and 3 also have the GCD-ness of 4, so you may also print 2 or 3.

Sample Input 3 

5 1000 1000 1000 1000 1000

Sample Output 3

1000

解题思路：拿到手，第一眼(没看题)看了输入的形式加上有个GCD我还以为要靠贝祖定理了呢，然后仔细分析是求一个K，K满足两个条件

①：K是输入的数组的元素的公因数，且从2开始。

②：k的倍数的数最多(当然这样的话就会有很多情况，随便输出一种情况就行)

 再一看数据，这么小直接二重循环暴力出来啦，外层循环从2开始，一直到1000，内次循环遍历数组，每次内存循环记录满足倍数条件的个数

Code:

#include
#include
#include
#include
using namespace std;
 
int a[1005];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i