시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB3421118840.553%

문제

하나의 $K$자리 수를 원하는 만큼 연속해서 이어 붙인 뒤, 뒤에서부터 $0$개 이상의 연속된 숫자를 제거하여 만들어낸 $K$자리 이상의 수를 $K$-반복수라 한다. 가령, $2\,462\,462$는 $3$자리 수 $246$을 세 번 이어 붙인 뒤, 마지막 두 자리 숫자를 제거하여 만들어낸 $3$-반복수이며, $24$는 $3$자리수 미만의 수이므로 $3$-반복수가 아니다.

$A$ 이상 $B$ 이하의 $K$-반복수 중, $M$으로 나누어 떨어지는 수의 개수를 구해보자.

입력

첫째 줄에 정수 $A,B,K,M$이 공백으로 구분되어 주어진다. $(1\le A\le B\le 10^{12};$ $1\le K\le 6;$ $1\le M\le 10^{12})$

출력

$A$ 이상 $B$ 이하의 $K$-반복수 중, $M$으로 나누어 떨어지는 수의 개수를 출력한다.

예제 입력 1

100 120 2 1

예제 출력 1

2

예제 입력 2

200 300 2 3

예제 출력 2

3

예제 입력 3

100 10000 3 3

예제 출력 3

600

노트

$10^{12}$는 $32$bit 정수형 타입 변수 범위를 초과할 수 있으므로, C/C++의 long long, Java의 Long 등 $64$비트 정수형 타입을 사용해야 한다.

출처

University > DGIST > 2024 DGIST 알고리즘 경진대회 C번