시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB344554629.487%

문제

당신은 상온 상압 초전도체를 개발하고 세상을 뒤바꿀 논문을 작성했다. 당신은 $N\mathrm{g}$의 초전도체 덩어리를 가지고 있는데, 논문 검증을 위해 $K$개의 연구소에서 초전도체 샘플을 요청했다! 각 연구소에는 $1\mathrm{g}$ 이상의 초전도체 샘플을 보내주면 된다. 다행히도, 당신은 초전도체를 정밀하게 부수는 기술을 가지고 있다. $2$ 이상의 정수 $a$에 대하여, $a\mathrm{g}$의 초전도체를 다음과 같은 방법으로 절단할 수 있다.

  • $1$ 이상 $a$ 미만의 정수 $b$를 선택한다.
  • $b\mathrm{g}$ 짜리 초전도체와 $(a-b)\mathrm{g}$짜리 초전도체 두 개로 쪼갠다.
  • 이때, $a$원의 비용이 든다.

연구 비용 절감을 위해 초전도체를 $K$개의 조각으로 자르기 위한 최소 비용은 얼마일지 구해야 한다. 단, 제한 조건하에서 위의 방법을 통해 초전도체를 $K$개의 조각으로 쪼갤 수 있음을 증명할 수 있다.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.

$T$ 개의 줄에 이어, 각 테스트 케이스마다 한 줄에 초전도체 덩어리의 무게 $N$과 초전도체 샘플을 요청한 연구소의 수 $K$가 공백을 사이에 두고 주어진다.

출력

각 테스트 케이스마다 초전도체를 $K$개의 조각으로 자르기 위한 최소 비용을 출력한다.

제한

  • $1 \leq T \leq 100\,000$
  • $2 \leq K \leq N \leq 1\,000\,000\,000$
  • 주어지는 모든 수는 정수이다.

예제 입력 1

3
2 2
5 3
10000 1000

예제 출력 1

2
7
19965

첫 번째 테스트 케이스의 경우, $2\mathrm{g}$짜리의 초전도체를 $1\mathrm{g}$짜리 초전도체 두 개로 부수는 것이 최적이다. 이 경우 총 $2$원의 비용이 든다.

두 번째 테스트 케이스의 경우, 다음과 같은 방법이 최적이다.

  • $5\mathrm{g}$짜리 초전도체를 $2\mathrm{g}$짜리 초전도체와 $3\mathrm{g}$짜리 초전도체로 부순다. 이때 $5$원의 비용이 든다.
  • $2\mathrm{g}$짜리 초전도체를 $1\mathrm{g}$짜리 초전도체 두 개로 부순다. 이때 $2$원의 비용이 든다.

따라서 총 $7$원의 비용이 들고, 더 적은 비용을 사용하는 방법이 없음을 증명할 수 있다.

출처

School > 경기과학고등학교 > 나는코더다 송년대회 > 나는코더다 2023 송년대회 H번