[PS] 백준 10166번 관중석

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

동심원의 선위에 좌석을 배치하는데, 각도가 같은 위치에 있는 좌석들은 맨 앞 좌석에 의해 가려진다.
그래서 각 좌석의 각도를 구해놓고 비교해야 하는데, 소수로 나타내면 정밀도 문제로 비교할 수가 없다.
그렇다면? 기약분수로 나타내자.

잠시 잊고 있었을 수 있지만 기약분수는 분모와 분자의 최대공약수로 분모와 분자를 나누어 주면 구할 수 있다.
유클리드 호제법을 이용해 최대공약수를 구하면 되겠다.

#include <iostream>

using namespace std;

int d1, d2, ans;
bool seats[2001][2001];

int gcd(int x, int y) {
	return y == 0 ? x : gcd(y, x % y);
}

int main() {
	cin >> d1 >> d2;

	for (int denominator = d1; denominator <= d2; denominator++) {
		for (int numerator = 0; numerator < denominator; numerator++) {
			int g = gcd(denominator, numerator);
			if (seats[numerator / g][denominator / g]) {
				continue;
			}
			ans++;
			seats[numerator / g][denominator / g] = true;
		}
	}

	cout << ans << '\n';
}