[백준] 2725번 : 보이는 점의 개수 (C++)

2725번 : 보이는 점의 개수

---

문제)

(0,0)에서 보이는 (x,y)의 개수를 구하려고 한다.(x,y >= 0, 정수)

 

(0,0)에서 (x,y)가 보이려면 (0,0)과 (x,y)를 연결하는 직선이 다른 점을 통과하지 않아야 한다. 예를 들어 (4,2)는 (0,0)에서 보이지 않는다. 그 이유는 (0,0)과 (4,2)를 연결하는 직선이 (2,1)을 통과하기 때문이다. 아래 그림은 0 <= x,y<=5인 경우에 (0,0)에서 보이는 점의 개수이다. 단, (0,0)은 계산하지 않는다.

 

 

N이 주어졌을 때, 원점에서 보이는 (x,y) 좌표의 개수를 출력하시오. (0 <= x,y <= N)

 

 

 

입력 :

첫째 줄에 테스트 케이스의 개수 C(1<=C<=1,000)가 주어진다. 각 테스트 케이스는 자연수 N(1<=N<=1,000) 하나로 이루어져 있고, 한 줄에 하나씩 주어진다.

 

 

 

출력 :

각 테스트 케이스에 대해 한 줄에 하나씩 (0,0)에서 보이는 점(x,y)의 개수를 출력한다.

 

 

 

 

 

풀이)

// 2725. 보이는 점의 개수
#include <iostream>
#include <vector>
 
using namespace std;
 
int get_gcd(int a, int b)
{
    while (a % b != 0)
    {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return b;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
    cin >> t;
 
    // 테스트케이스의 수와 범위가 1000이기 때문에 미리 모든 값을
    // 구해놓고 답만 계속 출력해주어야 시간초과가 나지 않는다.
 
    // 초기 값
    vector<int> vec{ 0, 3 };
 
    for (int i = 2; i <= 1001; i++)
    {
        int cnt = 0;
 
        // 보이는 점은 대칭으로 존재하므로,
        for (int j = 1; j < i; j++)
        {
            // 두 수가 공약수가 1이라면 보이는 수이다.
            if (get_gcd(i, j) == 1) cnt++;
        }
        vec.push_back(cnt + vec[i - 1]);
    }
 
    while (t--)
    {
        int n;
        cin >> n;
        cout << vec[n] * 2 - 3 << '\n';
    }
 
    return 0;
}
 

 

---

출처 : https://www.acmicpc.net/problem/2725 

2725번: 보이는 점의 개수