사과의 개수
시간 제한1초메모리 제한128 MB
최대 10^15까지의 범위 [A,B]에서 각 수를 연속된 같은 숫자 그룹으로 나눠 계산한 값의 합을 자릿수 DP로 구하는 문제입니다.
문제
한 마을의 큰길에는 사과나무가 한 줄로 서 있다. 첫 번째 나무의 번호는 1이고, 이후 나무들은 차례대로 번호가 붙어 있다.
나무 번호 N에 대해, N의 십진수 표현을 같은 숫자가 연속되는 최대 구간들로 나눈다. 숫자 d가 L번 연속되는 구간은 d \times L^2개의 사과를 기여한다. 그 나무에 열린 사과의 개수는 모든 구간의 기여를 더한 값이다.
두 나무 번호 A와 B가 주어진다. A번부터 B번까지 모든 나무에 열린 사과의 총개수를 구하시오.
입력
첫째 줄에 두 정수 A와 B가 주어진다.
1 \le A \le B \le 10^{15}
출력
A번부터 B번까지의 나무에 열린 사과의 총개수를 양 끝 번호를 포함하여 출력한다.