BOJ 10166번 관중석

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

\(1\leq{D1}\leq{D2}\leq{2000}\)

이 문제는 가운데에 콘서트장이 있고 그 주위로 동심원들이 있을 때, D1, D2가 입력으로 주어지면

각 원내에서 거리가 일정하게 D1, D1+1, D1+2, D1+2, ... , D2 개를 각각 놓고 싶을 때 겹치는 위치가 있다면

앞이 잘 보이지 않으므로 맨 앞에 한 좌석만 남기고 뒤에 좌석은 배치하지 않는 것이다.

이 때 총 필요한 좌석의 수를 구하는 문제이다.

사실 동심원이 여러개 있는 것이 아니라 원이 하나 있고 그 안에 거리가 일정하도록 D1개의 점을 찍고

그 다음에 같은 원에 거리가 일정하도록 D1+1개의 점을 찍고 를 계속 반복했을 때 찍히는 점의 수를 구하는 것과 같다.

우선 원의 둘레 길이를 1이라고 해보자. 그리고 북쪽에 있는 좌석을 기준점으로 두자.

그리고 거리가 일정하게 좌석 개수를 몇개씩 놓든 어차피 기준점에는 무조건 좌석을 놓으므로 기준점에 놓는 좌석은

생각하지않고 마지막에 1만 더해주는 식으로 하면 된다.

그러면 거리가 일정하게 D1개의 좌석을 놓고 싶다면 놓을 좌석들의 기준점으로부터 시계방향으로의 거리는

\(\frac{1}{D1}\) \(\frac{2}{D1}\) ... \(\frac{D1-1}{D1}\) 가 될 것이다. 

그리고 이 분수 값들을 모두 기약분수로 나타내 보면 분모가 D1보다 작아지는 값들이 있을 것이다.

예를 들어 D1이 짝수 일때는 분모가 \(\frac{D1}{2}\) 인 것이 있을 것이다.

그런데 잘 생각해 보면 분모가 \(\frac{D1}{2}\) 인 것들을 모두 모으면, 거리가 일정하게 \(\frac{D1}{2}\) 개를 

놓는 경우 놓는 좌석과 정확히 일치하게 된다. 즉, 좌석을 놓을 때마다 분모를 기록해둔다면

분모를 보면 이전에 놓았었는지를 알 수가 있는 것이고, 이미 놓았던 분모이면 놓지 않으면 되는것이다.

그러면 문제는 간단해진다. D1부터 D2까지 반복하는데 각각의 경우에 1부터 D-1 까지 순회하며

분자 분모로 놓고 기약분수로 만든다. 기약분수로 만드는건 두 수의 gcd로 분모를 나누면 되므로 간단하다.

그리고 이 분모가 표시되어있다면 continue 아니라면 답++ 그리고 다른데에 이 분모를 저장해두었다가

D-1까지의 계산이 모두 끝나고나서 다른데에 저장해둔 분모들을 놓았었다고 표시한다.

이게 끝이다.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int D1, D2;
map<int,int> mp1;
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
int main() {
    scanf("%d%d",&D1,&D2);
    int ans = 0;
    for(int i = D1; i <= D2; i++){
        map<int,int> mp2;
        for(int j = 1; j < i; j++){
            int g = gcd(i, j);
            if(mp1[i / g]) continue;
            ans++;
            mp2[i / g] = 1;
        }
        for(auto p : mp2) mp1[p.first] = 1;
    }
    printf("%d", ans+1);
    return 0;
}