2725: 보이는 점의 개수-GCD 유클리드호제법

https://www.acmicpc.net/problem/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)의 개수를 출력한다.

예제 입력 1 복사

4
2
4
5
231

예제 출력 1 복사

5
13
21
32549

 

 

---

 

 

(0,0)에서 (x,y)까지 직선을 그렸을 때, 그 직선이 다른 정수 점을 지나지 않는 경우만 카운트해야 합니다.

y=ax의 직선이 다른 정수 점을 안 지나려면, x와 y의 최대공약수가 1인 서로소여야 하므로 gcd가 1인 점을 찾았습니다.

# 첫 번째 줄에서 테스트 케이스 개수 입력
C = int(input().strip())

# 테스트 케이스 개수만큼 입력 받기
test_cases = [int(input().strip()) for _ in range(C)]


for t in test_cases: #2, 4, 5, 231
    cnt =0
    for i in range(1,t+1): #2번   #테스트 케이스-최대공약수가 1인 경우
        for j in range(1,t+1):
            a,b =i,j
            while b:
                (a,b)=(b,a%b)
            if(a==1):
                cnt+=1  
    print(cnt+2)

 

(1,0)과 (0,1) 두 개의 점을 고려해야 하기 때문에 +2를 했습니다.

 

실제 코드에서는 아래처럼 dp를 사용하고, 반을 나눠서 계산해야 성공이 뜹니다.

import sys
import math

input = sys.stdin.readline

# 최대 1000까지의 값을 미리 계산하여 DP 테이블을 채움
dp = [0] * 1001
dp[1] = 3  # x = 1일 때 결과값 설정

for x in range(2, 1001):
    count = 0
    for y in range(1, x):
        if math.gcd(x, y) == 1:  # 최대공약수가 1이면
            count += 1

    dp[x] = dp[x - 1] + count * 2  # 대칭되는 경우도 포함해서 2배로 계산

# 입력값 처리 및 결과 출력
C = int(input().strip())

for _ in range(C):
    t = int(input().strip())
    print(dp[t])