홍준 프로그래밍 대회 C++ - 백준 1222

https://www.acmicpc.net/problem/1222

문제 접근

팀당 인원은 무조건 참가하는 대학 인원들의 $GCD$로 설정해야 한다.

$GCD$로 설정해야 남는 인원 없이 팀을 구성할 수 있기 때문이다.

따라서 답은 $GCD(구성하는모든팀)$ $\cdot\;(팀개수)$이다.

$GCD$는 어떤 수의 약수이기 때문에,

모든 대학의 약수들의 개수를 관리해주면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n,tmp;
ll ans=0;
unordered_map<int,int> um;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    um[1]=n;
    while(n--){
        cin >> tmp;
        if(tmp==1) continue;
        if(um.find(tmp)!=um.end()) um[tmp]++;
        else um[tmp]=1;
        int cnt=sqrt(tmp);
        for(int i=2;i<=cnt;i++){
            if(tmp%i==0){
                if(um.find(i)!=um.end()) um[i]++;
                else um[i]=1;
                if(tmp/i!=i){
                    if(um.find(tmp/i)!=um.end()) um[tmp/i]++;
                    else um[tmp/i]=1;
                }
            }
        }
    }
    for(auto it=um.begin();it!=um.end();it++){
        if(it->second!=1) ans=max(ans,(ll)it->first*(ll)it->second);
    }
    cout << ans;
    return 0;
}

$p.s$ 약수 개수를 관리하면 시간이 매우 오래걸린다. 될 수 있는 모든 수에 대해 그 배수의 개수를 곱해주면 답이 되기 때문에 이 방법이 더 나은 방법이다.

#include <bits/stdc++.h>
#define SIZE 2000001
typedef long long ll;
using namespace std;

int n,cnt[SIZE],tmp;
ll ans=0;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    while(n--){
        cin >> tmp;
        cnt[tmp]++;
    }
    for(int i=1;i<SIZE;i++){
        ll s=0;
        for(int j=1;i*j<SIZE;j++) s+=(ll)cnt[i*j];
        if(s<2) continue;
        ans=max(ans,(ll)i*s);
    }
    cout << ans;
    return 0;
}