백준 27172번 수 나누기 게임 C++ (골드5)

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

 

다른 수와 비교하여 내가 다른 수의 약수이면 1점을 얻고, 내가 다른 수의 배수이면 1점을 잃는 게임이다.

n이 최대 10만이기때문에 두개씩 짝지어서 전부 비교하면 시간초과가 날 것이기 때문에 다른 방법을 사용해야 한다.

 

모든 수를 순회하며 약수를 구하고, 약수를 순회하며 만약 약수가 다른 카드에 존재하면 해당 카드는 1점을 얻고 본인은 1점을 잃는다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    vector<int> v(n);
    map<int, int> ans;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        ans.insert({ v[i],0 });
    }
    for (int i = 0; i < n; i++)
    {
        int value = v[i];
        set<int> s;
        for (int j = 1; j * j <= value; j++) {

            if (j * j == value) {
                s.insert(j);
            }
            else if (value % j == 0) {
                s.insert(j);
                s.insert(value / j);
            }
        }
        for (auto a : s)
        {
            if (ans.find(a) == ans.end()) continue;
            ans[value]--;
            ans[a]++;
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << ans[v[i]] << " ";
    }
}