[BOJ] 1241 - 머리 톡톡

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

BOJ - 머리 톡톡

문제 유형: 수학, 정수론

문제 난이도: Gold V

시간 제한: 2초

메모리 제한: 128MB

 

문제

엄지 생일 기념으로 학생들은 파티를 하고 있다. 엄지는 N(1≤N≤100,000)명의 학생에게 1부터 N번까지 차례대로 번호를 부여하였고 그들을 순서대로 빙 둘러앉아 원을 만들게 하였다. (즉 i번째 학생은 i-1과 i+1학생 사이에 앉아있다. 단, N번째 학생은 N-1번째 학생과 첫 번째 학생 사이에 앉아있다.)

N명의 학생은 둘러앉아 "머리톡톡" 게임을 하려한다. 게임 규칙은 다음과 같다. 각각의 학생은 자신의 머리 위에 1,000,000 이하의 자연수 중 하나를 쓴다. 그리고 1번부터 N번 학생까지 한 명씩 차례대로 일어나 원을 돌면서 자신이 쓴 숫자가 다른 사람이 쓴 숫자의 배수이면 그 학생의 머리를 "톡톡" 친다.

문제는 각각의 학생이 일어나 자신의 자리로 돌아올 때까지 총 몇 명의 학생의 머리를 치는지 구하는 것이다.

 

입력

첫째 줄에 학생의 수 N이 입력되고 다음 N개의 줄에는 1번부터 N번까지 각각의 학생이 자신의 머리에 쓴 숫자를 입력받는다.

 

출력

총 N개의 줄로 i번째 줄에는 i번째 학생이 한 바퀴를 돌면서 머리를 친 학생의 수를 출력한다.

 

풀이

모든 수들에 대해서 <수-개수>쌍을 만든다.

각각의 쌍에 대해서, 에라토스테네스의 체와 같이 자신의 배수들에 대해서 자신의 개수만큼 카운트를 누적시킨다.

자기자신에 대해서는 <개수-1>만큼 누적한다.

 

순차적으로 수별로 자신의 약수들의 개수를 출력하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;

    vector<int> a(n);
    unordered_map<int, int> num_count;
    for (int &i : a) {
        cin >> i;
        num_count[i]++;
    }

    vector<int> number_of_divisors(1000001, 0);
    for (const auto &[k, v] : num_count) {
        number_of_divisors[k] += v - 1;
        for (int i = k * 2; i <= 1000000; i += k) {
            number_of_divisors[i] += v;
        }
    }

    for (const auto &num : a) {
        cout << number_of_divisors[num] << "\n";
    }

    return 0;
}