BOJ 1222

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

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

1 ~ 2000000 수가 각각 몇번 등장하는지를 나타내는 배열 cnt를 전처리해준다.

1 <= i <= 2000000 인 모든 i에 대해 i의 배수에 해당하는 cnt의 값을 모두 더하면 그게 참가하는 학교 수가 되고

ans = max(sum(cnt[i의 배수]) * i, ans)로 업데이트 해준다.

시간복잡도는 O(N log N) 이 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define _unique(v) (v).erase(unique((v).begin(), (v).end()), (v).end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define xx first
#define yy second
#define ll long long
const int INF = 2e9;
const ll mod = 998244353;
const double eps = 1e-9;

int n;

void solve() {
    cin>>n;
    int arr[2000010] = {0,};
    for(int i=0;i<n;i++){
        int x;cin>>x;
        arr[x]++;
    }
    ll ans = 0;
    for(int i=1;i<=2000000;i++){
        ll sum = 0;
        for(int j=i;j<=2000000;j+=i){
            sum+=(ll)i*arr[j];
        }
        if(sum==i) continue;
        ans=max(ans, sum);
    }
    cout<<ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(10);

#ifndef ONLINE_JUDGE
    freopen("./input.txt", "r", stdin);
    clock_t _st_t = clock();
#endif

    int tt = 1;
    //cin>>tt;
    while(tt--){
        solve();
        cout<<'\n';
    }

#ifndef ONLINE_JUDGE
    cerr << endl << endl << (double) (clock() - _st_t) / (double) CLOCKS_PER_SEC << "sec" << endl;
#endif

    return 0;
}