BOJ 27172 - 수 나누기 게임

 

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

27172번: 수 나누기 게임

본 문제의 핵심은, $x_i$를 가진 사람이 점수를 얻으려면 $p\times x_i$ ($p$는 $2$보다 크거나 같은 정수)가 존재해야 합니다.

 

즉, $1$보다 크거나 같고, $1,000,000$보다 작거나 같은 정수 범위 내에서 $x_i$를 가진 사람이 얻을 수 있는 점수(+)는, 이 범위 내에서의 $p\times x_i$를 가진 사람의 수 입니다.

잃는 점수는 이 사람의 수를 구하는 과정에서 $p\times x_i$를 가진 사람의 점수를 $-1$하면 됩니다.

 

bool exist[1000005];
int arr[100005];
int score[1000005];
int main() {
    fastio();
    int N;
    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> arr[i];
        exist[arr[i]]=true;
    }
    for(int i=0; i<N; i++) {
        for(int j=arr[i]*2; j<=1000000; j+=arr[i]) {
            if(exist[j]) {
                score[arr[i]]++;
                score[j]--;
            }
        }
    }
    for(int i=0; i<N; i++) {
        cout << score[arr[i]] << ' ';
    }
}