DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

선분 위의 격자점

문제로 돌아가기

해설

dx=∣x2−x1∣d_x=|x_2-x_1|dx​=∣x2​−x1​∣, dy=∣y2−y1∣d_y=|y_2-y_1|dy​=∣y2​−y1​, g=gcd⁡(dx,dy)g=\gcd(d_x,d_y)g=gcd(dx​,dy​)라 하자. 두 점이 다르므로 g>0g>0g>0이다. 방향 벡터를 ggg로 나누면 두 성분이 서로소인 정수 벡터가 된다. 따라서 선분 위 격자점은 A+k(B−A)/gA+k(B-A)/gA+k(B−A)/g (0≤k≤g0\le k\le g0≤k≤g)이며, 양 끝점을 제외하면 정답은 g−1g-1g−1이다. 한 성분이 0인 수평·수직 선분에도 같은 식이 성립한다.

서브태스크 1은 정수 xxx 좌표를 순회하며 (x−x1)(y2−y1)(x-x_1)(y_2-y_1)(x−x1​)(y2​−이 로 나누어떨어지는지 검사한다. 수직 선분은 별도로 계산한다. 케이스당 이므로 전체 최대 약 번의 검사가 필요하다.

서브태스크 2는 유클리드 호제법으로 최대공약수를 구한다. 전체 시간 복잡도는 O(Tlog⁡(2⋅109))O(T\log(2\cdot10^9))O(Tlog(2⋅109)), 추가 공간은 O(1)O(1)O(1)이다.

좌표 차이의 절댓값은 최대 2⋅1092\cdot10^92⋅109, 정답은 최대 1 999 999 9991\,999\,999\,9991999999999이다. 나이브 풀이의 곱의 절댓값도 4⋅10184\cdot10^{18}4⋅10 이하이므로 모든 계산은 부호 있는 64비트 정수로 안전하다.

∣
y1​
)
x2−x1x_2-x_1x2​−x1​
O(∣x2−x1∣+1)O(|x_2-x_1|+1)O(∣x2​−x1​∣+1)
400 000400\,000400000
18