BOJ-2725 보이는 점의 개수

필요한 지식

1. 최대 공약수

접근

보이는 점의 개수 찾기

• (0,0) 에서 보이는 점의 개수를 찾아야한다.

• 두점을 비교한다고 가정했을 때 (0,0)에서 선을 그어보면 그 선분이 겹치면 둘 중 하나의 점은 (0,0)에서 볼수가 없는 점이다.

• 선분이 겹친다는 의미는 기울기가 같다는의미 이며, 그 기울기가 같은 선분중 (0,0)에서 보이는 점은 기울기가 기약분수로 나타나는 경우이다.

• 기울기가 기약분수로 나타내는 경우는 분모와 분자의 기울기의 최대공약수가 1인 경우 이다.

• 즉, 모든 점에서 (0,0)과의 선분을 그어보고 그 기울기가 기약분수로 나타내는 경우 체크해주면 된다.

개수 출력 하기

• (a,b) 점을 저장할 때 2차원 배열이 아닌 1차원 배열의 max(a,b) 인덱스에 저장해 주면된다.

• 테스트케이스가 최대 1000개 존재하므로 위에서 저장한 1차원 배열을 구간합 배열로 바꿔주고 상수시간만에 처리하게 했다.

코드(C++)

#include <iostream>
#include <algorithm>
#define FIO ios_base::sync_with_stdio(0), cin.tie(), cout.tie();
using namespace std;
int arr[1001], t, x;
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int main() {
	FIO;
	cin >> t;
	for (int i = 0; i <= 1000; i++) {
		for (int j = 0; j <= 1000; j++) {
			if (gcd(i, j) == 1) arr[max(i, j)] += 1;
		}
	}
	for (int i = 1; i <= 1000; i++) arr[i] += arr[i - 1];
	while (t--) {
		cin >> x; cout << arr[x] << "\n";
	}
	return 0;
}

결과