백준 1222 : 홍준 프로그래밍 대회

1222번: 홍준 프로그래밍 대회 (acmicpc.net)

1222번: 홍준 프로그래밍 대회

풀이

1. 각 팀원들의 약수를 모두 구해 해당 약수들의 개수를 구하고 약수의 개수 * 해당 약수의 값이 가장 큰 값을 찾으려함
-> 약수를 구하는데 sqrt(n)의 시간복잡도가 들어 약 2e8정도의 시간복잡도가 나옴 = AC를 받았으나 빡빡함
2. 1~200만까지의 각 수들의 약수들을 모두 구해놓고 수를 입력받으면 약수들의 개수를 세주는 방법
시간은 nlogn이였으나 약수가 많아 메모리초과가 남
3. 2번을 응용하여 입력받을 때 숫자들의 개수를 기록해놓고 1~200만을 순회하면서 해당 수를 약수로 갖는 수가 몇개인지를 찾음. -> nlogn 의 시간복잡도로 무사히 통과가능

 

시간복잡도 O(NlogN) => N + N/2 + N/3 + N/4 + ... + N/N = N(1 + 1/2 + 1/3 + 1/4 + 1/5 + ... + 1/N), N<=2e6

#include<bits/stdc++.h>
#include<time.h>


#define MAX 5000001
#define INF 2000000000
#define MOD 1000000
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }


#define SIZE 2000001
ll cnt[SIZE];
ll num[SIZE];
int main() {
    init();
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        ll k; cin >> k;
        num[k]++;
    }
    for (int i = 1; i < SIZE; i++) {
        for (int j = i; j < SIZE; j += i) {
            cnt[i] += num[j];
        }
    }
    ll ans = n;
    for (int i = 2; i < SIZE; i++) {
        if(cnt[i]>1)
            ans = max(ans, cnt[i] * i);
    }
    cout << ans << "\n";
}