ZOJ Problem Set - 3448
Doraemon plays game with Nobita one day.
Doraemon gives a number x with length n in base B, then Doraemon removes one digit from number x, the location of this digit is from s to t (3 ≤ s ≤ t ≤ n). We call the leftmost digit of x the first digit, the rightmost digit of x the nth digit. After removing one digit, we get a number y in base B. Nobita should answer the number of possible values of x which follows the constraint that there exists a corresponding y after removing a digit so that x is divisible by y.
Nobita also wants Doraemon to solve a similar problem. But Nobita is not good at arithmetic, he can only remove the first digit of x to form a new number y. Then Doraemon should answer the number of possible values of x whose corresponding y is a divisor of x.
Input contains multiple cases (1 ≤ case_num ≤ 2000). Process to the end of file. Each case gives the length of the number n(3 ≤ n ≤ 100), base B(2 ≤ B ≤ 32), start position s and end position t(3 ≤ s ≤ t ≤ n) in a single line separated with a single space.
Output contains two numbers separated by a single space, the first is Doraemon's answer, and the second number is Nobita's answer.
3 10 3 3
Author: QU, Zhe
Contest: ZOJ Monthly, December 2010