[골5] 27172 - 수 나누기 게임

#include <iostream>
#include <algorithm>
#include <vector>

#pragma region 빠른 입출력

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

using namespace std;

#define MAX 1000001

int main()
{
	FAST_IO();
	int n;
	cin >> n;
	vector<int> v(n);
	int scores[MAX]{ 0 }, cards[MAX]{ 0 };

	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
		cards[v[i]] = 1;
	}

	// 에라토스테네스의 체 응용
	for (int i = 0; i < n; i++)
	{
		// 해당 카드 탐색
		int val = v[i];

		for (int j = val * 2; j < MAX; j += val)
		{
			// 해당 배수의 카드가 존재하면
			if (cards[j] == 1)
			{
				scores[val]++;
				scores[j]--;
			}
		}
	}
	for (int i = 0; i < n; i++)
		cout << scores[v[i]] << ' ';

	return 0;
}