주어진 K와 C에 대해, K를 K번 쓰는 대신 K+A를 K+A번 쓸 때 절약되는 문자 수에서 C 곱하기 A를 뺀 값을 최대로 하는 양의 정수 A를 찾는다.
어려움9문자열 매칭수학정수론그리디아직 제출이 없습니다시간 제한1초메모리 제한128 MB인섭이는 현우가 낸 과제를 시작하려 한다. 하지만 K를 K번 쓰는 일은 너무 힘들었다. 어떻게 할까 고민하던 인섭이에게 좋은 아이디어가 하나 떠올랐다. K+A (A>0)가 K+A번 등장하는 문자열을 쓰고, 더 큰 수가 더 많이 등장했으니 원래 과제보다 어려운 문제를 풀어 왔다고 현우를 설득하는 것이다. 이 과정에서 써야 하는 글자 수가 L만큼 줄어들면 인섭이는 L만큼의 만족도를 얻는다.
하지만 인섭이는 현우가 낸 과제를 정확하게 해결하지 않는 데 양심의 가책을 느낀다. K를 K번 쓰는 대신 K+A를 K+A번 적는다면 A에 비례해 양심의 가책을 느낀다. 정확히는 어떤 상수 C에 대해 C×A만큼의 가책을 느낀다.
인섭이는 얻은 만족도에서 양심의 가책을 뺀 값을 최대로 만들려 한다. 이 값이 얼마인지 찾아주자.
인섭이가 작성할 문자열에는 수가 겹쳐서 등장할 수도 있다. 예를 들어 문자열 12312312에는 12312가 2번 등장하며, 333333에는 3333이 3번 등장한다.
문제에서 설명한 정수 K와 C가 공백으로 구분되어 주어진다. (1≤K≤1012, 0≤C≤105)
문제의 정답을 한 줄에 출력한다. 모든 양의 정수 A에 대해 값이 0 이하라면 0을 출력한다.
K=10, C=2인 경우를 보자. 10을 10번 쓰면 모두 20글자를 써야 한다. 하지만 11을 11번 쓰면 12글자만 쓰게 되고, 이때 만족도는 8, 양심의 가책은 (11−10)×2가 되어 정답은 8−2=6이다.