만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

실 전화기

시간 제한0.5초메모리 제한1024 MB

요약
원 위에 앉은 N명과 간격 K가 주어질 때, i번과 i+K번을 잇는 현 중 원 안에서 서로 교차하는 쌍의 개수를 구합니다.
난이도

보통10점 중 7점

유형
수학, 정수론, 기하
정답자
아직 제출이 없습니다

문제

2023 shake! 대회가 끝나고 참가자들의 뒤풀이 행사가 시작되었다. 참가자들은 바닥에 거대한 원을 그린 뒤 원의 둘레를 따라 같은 간격으로 자리에 앉았다. 이대로 뒤풀이를 진행하려 했으나, 서로 너무 멀리 떨어진 사람끼리는 목소리가 잘 전달되지 않는다는 사실을 깨달았다.

이를 해결하기 위해 당신은 실 전화기로 사람들의 소통을 돕기로 했다. 구체적으로 다음 순서를 따르는 시행을 거쳐 사람들을 이어준다.

  1. 11번 이름표를 당신에게 붙인 뒤, 시계 방향으로 사람들에게 순서대로 22번부터 NN번까지 이름표를 붙여준다.
  2. 11번 이름표를 가진 사람(즉, 당신)을 선택한다.
  3. 선택한 참가자와 그로부터 시계 방향으로 KK번째에 위치한 참가자를 선분으로 잇고, 그 선분을 따라 실 전화기를 팽팽하게 연결한다.
  4. 선택했던 참가자로부터 시계 방향으로 KK번째에 위치한 참가자를 선택한다.
  5. 새로 선택한 참가자가 이전에 한 번이라도 선택되었던 참가자라면 시행을 종료한다. 그렇지 않다면 3번 시행으로 돌아간다.

그런데 서로 다른 두 실 전화기가 교차하면 목소리 전달이 방해된다는 사실을 알게 되었다. 참가자 수 NN과 정수 KK가 주어질 때, 원의 내부에서 서로 교차하는 실 전화기 쌍의 수를 구하라. 단, 사람이 위치한 곳에서는 실 전화기가 서로 만나지 않는다.

입력

첫째 줄에 참가자의 수 NN과 정수 KK가 공백으로 구분되어 주어진다. (1≤K<N≤109)(1\leq K < N\leq 10^9)

출력

첫째 줄에 원의 내부에서 서로 교차하는 실 전화기 쌍의 수를 출력한다.

힌트

한 점에 세 개 이상의 실 전화기가 만났을 때는 교차하는 실 전화기 쌍의 수가 하나가 아니므로 주의하라.

동일한 참가자 둘 사이를 이어주는 서로 다른 두 선분은 내부에서 교차하지 않는 것으로 간주한다.

예제3

  1. 예제 1

    입력
    5 2
    
    예상 출력
    5
    
  2. 예제 2

    입력
    8 3
    
    예상 출력
    16
    
  3. 예제 3

    입력
    3 1
    
    예상 출력
    0