BOJ)1222 홍준 프로그래밍 대회

문제: icpc.me/1222

문제를 해석하면 만약 홍준이가 팀원의 수를 k명이라 정했다면 학교 사람의 수가 k로 나누어 떨어지는 학교만 참가할 수 있다.

즉 주어진 수들을 전부 소인수 분해를 하였을 때 i를 소인수로 가진 학교의 개수를 a[i]라고 하면, a[i]가 2이상인 경우에서의 i*a[i]의 최댓값이 답이 된다.

하지만 모든 수의 소인수를 구할 경우 O(N*sqrt(N))으로 시간내에 들어오기에는 조금 무리가 있다.

하지만 수를 받으면서 소인수를 계속 연산하는 방법이 아닌 수를 전부 받아놓고 하나의 수에는 한번의 계산만 하는 방법으로 최적화 시켜 시간내에 통과시킬 수 있다.

이보다 좋은 방법은 모든 수 i에 대하여 자신을 소인수로 가지는 수를 직접 계산해주는 방법이다. 이 방법은 소스코드로 설명을 대체한다.

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,x,res,a[2000020];
int main(){
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",&x);
        a[x]++;
    }
    for(ll i=1;i<=2000000;i++){
        ll cnt=0;
        for(ll j=i;j<=2000000;j+=i)
            cnt+=a[j];
        if(cnt>1)
            res=max(res,cnt*i);
    }
    printf("%lld\n",res);
    return 0;
}