문제 출처 : 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)

문제 해결 방법

100% 수학 문제다.

이 문제의 포인트는 최소공약수이다. 임의의 좌표 (x,y)에서 x와 y의 공약수가 1이면 중복되는 기울기가 존재하지 않는다.

예를 들어 (4,2)는 공약수가 2고 최대 공약수로 각 좌표를 나누면 결국 (2,1)가 되어 기울기가 겹치게 된다.

해당 방법으로 풀려고 했지만 통과하지 못했다.

1. 모든 기울기를 구해서 set에 담고 size를 출력하는 방식도 답은 나오지만 메모리초과가 발생한다.
2. 또한 테스트케이스 만큼 이중for문을 돌려도 시간초과가 발생한다.
   • 시간초과 코드

그래서 모든 경우를 미리 만들어놓고 테스트케이스마다 가져오는 방식으로 해결해야한다.

이 때 1부터 1000까지 정사각형의 모든 기울기를 구해야하는데 단순하게 이중for문으로 구하는 것은 불가능하다.

왜냐면 i가 1일 때 j는 1~1000까지 반복을 하기 때문이다. 우리가 원하는 정사각형까지 따로 구하는게 불가능하다.

그래서 이중for문의 로직을 살짝 바꿔야한다. 자세한 것은 코드를 보자.