cho.sh

통역사

아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

송죽국은 NN개의 도시로 이루어져 있는 평화로운 국가이다. 각 도시는 11번, 22번, ..., NN번과 같이 번호를 가지고 있다.

옛날에는 송죽국의 모든 도시가 공용어인 11번 언어를 사용했다고 전해진다. 그러나 시간이 흐름에 따라 도시마다 언어가 다르게 바뀌었다. 그 결과 지금 ii번 도시는 i+1i+1번 언어를 사용하게 되었다. 안타깝게도 11번 언어는 사어가 되어 아무도 구사할 수 없다.

어느 날, 송죽국의 KK번 도시에 큰 사건이 일어났다. KK번 도시의 시장은 이 사실을 다른 도시에 알리기로 했으나, 서로 다른 언어를 쓰는 두 도시가 말이 통하지 않는다는 문제에 부딪쳤다. 시장은 고민 끝에, KK번 도시를 제외한 모든 도시에 대해서 KK번 도시가 사용하는 언어를 그 도시가 사용하는 언어로 통역하는 N−1N-1명의 통역사를 고용하기로 했다.

한 명의 통역사는 아래와 같은 과정을 통해 한 언어를 다른 언어로 통역한다. 이때, 양의 정수 XX와 11보다 큰 정수 bb에 대해 XX의 bb진법 표현 \[x_j,x_j−1,...,x_1,x_0]\[x\_{j}, x\_{j-1}, ..., x\_{1}, x\_{0}]은 X=x_jbj+x_j−1bj−1+...+x_1b+x_0X=x\_{j}b^{j}+x\_{j-1}b^{j-1}+...+x\_{1}b+x\_{0}를 만족하는 정수 x_j,x_j−1,...,x_1,x_0x\_{j}, x\_{j-1}, ..., x\_{1}, x\_{0}로 구성된 배열이다. (0≤x_j,x_j−1,...,x_1,x_0<b,x_j≠0)(0 \le x\_{j}, x\_{j-1}, ..., x\_{1}, x\_{0} < b, x\_{j} \neq 0) XX의 bb진법 표현은 항상 유일하다.

  • 양의 정수 AA와 11보다 큰 정수 pp에 대해, AA의 pp진법 표현 \[a_k,a_k−1,...,a_1,a_0]\[a\_{k}, a\_{k-1}, ..., a\_{1}, a\_{0}]를 구한다.
  • maxa_k,a_k−1,...,a_1,a_0\text{max} \\{ a\_{k}, a\_{k-1}, ..., a\_{1}, a\_{0} \\}보다 큰 정수 qq에 대해, BB의 qq진법 표현이 \[a_k,a_k−1,...,a_1,a_0]\[a\_{k}, a\_{k-1}, ..., a\_{1}, a\_{0}]와 같아지는 양의 정수 BB를 구한다.
  • 통역사는 AA번 언어를 BB번 언어로 통역할 수 있으며, 이 통역사를 고용하는 데 드는 비용은 p+qp+q이다.

예를 들어, 11번 도시가 사용하는 22번 언어를 22번 도시가 사용하는 33번 언어로 통역하기 위해 A=2,p=2,B=3,q=3A=2, p=2, B=3, q=3을 선택할 수 있다. 22의 22진법 표현 \[1,0]\[1, 0]과 33의 33진법 표현이 같기 때문이다. 그리고 이때 드는 비용은 2+3=52+3=5이다.

송죽국을 이루는 도시의 수 NN과 사건이 일어난 도시의 번호 KK가 주어졌을 때, KK번 도시가 사용하는 언어를 나머지 도시가 사용하는 언어로 통역하는 N−1N-1명의 통역사를 고용하는 최소 비용을 구하여라.

입력

첫 번째 줄에 두 양의 정수 NN, KK가 공백을 사이에 두고 주어진다. (1≤K≤N≤106)(1 \le K \le N \le 10^{6})

출력

첫 번째 줄에 KK번 도시가 사용하는 언어를 나머지 도시가 사용하는 언어로 통역하는 N−1N-1명의 통역사를 고용하는 최소 비용을 구해 출력한다.