[백준] 1222 홍준 프로그래밍 대회

문제의 조건이 많다 

정리하자면

1) 학교는 N개이고, 학생은 A[i]...A[N]명

2) 대회의 팀은 1~200000까지 임의로 가능

3) 대회에 나가려면 같은 학교 학생끼리 팀을 해야함

4) 학교에서 대회를 나가려면 모든 학생이 팀에 포함되어 나가야 함

5) 학교 예선 1등만 본선에 가고 본선은 최소 2팀이상 나와야 함

대회에 나가려면 학교 학생의 공약수로 팀을 이뤄야 한다

그래야 모든 학생이 나갈 수 있다

그럼 모든 학교의 공약수를 미리 구해두고 

공약수 X 공약수를 가지는 학교의 최대값을 찾으면 된다!

이 때 공약수를 가지는 학교가 2이상만 가능하다

200만 X 20만 ==롱롱 필수

벡터로 구현했다가 메모리 터졌다 ㅎㅎ

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 2000002
#define ll long long
ll arr[MAXN];
int n;
void go(int x) {
    for (int i = 1; i*i <= x; i++) {
        if (x%i == 0) {
            arr[i]++;
            if (i != x / i) arr[x / i]++;
        }
    }
}
int main() {
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) {
        int x; scanf(" %d", &x);
        go(x);
    }
    ll ans = 0;
    for (ll i = 1; i < MAXN; i++) {
        if (arr[i] < 2) continue;
        ans = max(ans, arr[i]*i);
    }
    printf("%lld\n", ans);
}