수 나누기 게임
문제
문제가 길어서 요약.
각 플레이어는 1~1000000 사이의 카드르 한 장 씩 가지고 모든 사람과 결투를 한다.
결투를 했을 때 결과는 상대 숫자를 내 숫자로 나누면 +1, 나뉘면 -1이 된다.
게임이 끝나고 모든 플레이어의 점수를 구하라.
풀이
처음엔 예전에 풀었던 누적합으로 최대 공약수 했던 문제가 생각났다.
하지만 다른 문제인 것 같아서 어떻게 모든 숫자를 나눠볼 수 있지? 생각하다 소수 판별 방법으로
하면 되겠다고 생각했고, 에라토스테네스 체를 조금 변형해서 풀었다.
우선 check 배열에 입력 받은 값들을 넣어 어떤 숫자가 나왔는지 확인하고
plus 배열을 나누는 것에 성공했을 때, minus 배열은 여태까지 나온 숫자로 나뉘었을 때를 저장한다.
그 다음 plus - minus를 해주면 답이 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <queue>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
long long n, m, t;
int chk=0;
cin >> n;
vector<int> v(n);
vector<bool> check(1000001, 0); //나왔는지 체크용
vector<int> minus(1000001, 0); // 점수 차감용
vector<int> plus(1000001, 0); // 점수 증가용
for(int i=0;i<n;i++){
cin >> v[i];
check[v[i]]=1;
}
for(int i=0;i<n;i++){
for(int j=v[i];j<1000001;j+=v[i]){
if(check[j]){
minus[j]++;
plus[v[i]]++;
}
}
}
for(int i=0;i<n;i++){
cout << plus[v[i]]-minus[v[i]] << ' ';
}
return 0;
}