난이도

Gold 5

문제

《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다.

《수 나누기 게임》의 규칙은 다음과 같습니다.

게임을 시작하기 전 각 플레이어는 $1$부터 $1\,000\,000$ 사이의 수가 적힌 서로 다른 카드를 잘 섞은 뒤 한 장씩 나눠 가집니다. 매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 합니다. 결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나눴을 때, 나머지가 $0$이면 승리합니다. 플레이어의 카드에 적힌 수가 다른 플레이어의 카드에 적힌 수로 나누어 떨어지면 패배합니다. 둘 다 아니라면 무승부입니다. 승리한 플레이어는 $1$점을 획득하고, 패배한 플레이어는 $1$점을 잃습니다. 무승부인 경우 점수의 변화가 없습니다. 본인을 제외한 다른 모든 플레이어와 정확히 한 번씩 결투를 하고 나면 게임이 종료됩니다. 《수 나누기 게임》의 결과를 가지고 한별이와 내기를 하던 은하는 게임이 종료되기 전에 모든 플레이어의 점수를 미리 알 수 있을지 궁금해졌습니다. 은하를 위해 각 플레이어가 가지고 있는 카드에 적힌 수가 주어졌을 때, 게임이 종료된 후의 모든 플레이어의 점수를 구해주세요.

입력

첫 번째 줄에 플레이어의 수 $N$이 주어집니다.

두 번째 줄에 첫 번째 플레이어부터 $N$번째 플레이어까지 각 플레이어가 가지고 있는 카드에 적힌 정수 $x_{1}$, $\cdots$, $x_{N}$이 공백으로 구분되어 주어집니다.

출력

첫 번째 플레이어부터 $N$번째 플레이어까지 게임이 종료됐을 때의 각 플레이어의 점수를 공백으로 구분하여 출력해주세요.

예제 입력

3
3 4 12

예제 출력

1 1 -2

해설 및 후기

우선 각 카드가 등장했는지 여부를 판별하기 위해 1000001만큼의 배열을 선언해 O(N)의 속도로 전처리한다. 이후 각 플레이어의 카드를 순회하며 가능한 모든 배수를 만들어, 만약 등장한 적이 있다면 플레이어 카드의 값에 +1, 배수로 만들어진 카드의 값에 -1을 한다.

마지막으로 다시 입력을 순회하며 저장된 값을 출력한다.

제출 코드

isV = [[False,0] for _ in range(1000001)]
n = int(input())
l = list(map(int, input().split()))
for i in l:
    isV[i][0] = True

for i in l:
    tmp = 2
    while(tmp * i <= 1000000):
        if(isV[tmp*i][0]):
            isV[tmp*i][1] -= 1
            isV[i][1] += 1
        tmp += 1


for i in l:
    print(isV[i][1], end=' ')