PEG Judge - DWITE Oct '05 - Five Digit Divisibility

DWITE Online Computer Programming Contest
October 2005

Problem 5

Five Digit Divisibility

Using each of the digits 1, 2, 3, 4 and 5 exactly once to form 5 digit numbers, how many are divisible by 12?

First we note that 12 = 3×4; in other words, if a number is divisible by 12 it will be divisible by 3 and 4.

For a number to be divisible by 3, the sum of its digits must be divisible by 3: 1 + 2 + 3 + 4 + 5 = 15. As 15 is divisible by 3, ALL 5-digit numbers made up of the digits 1, 2, 3, 4, and 5 will be divisible by 3.

For a number to be divisible by 4, the last two digits must divide by 4. In our case, the number must end in: 12, 24, 32, or 52.

If the number ends in 12, the first three digits will be 3, 4, and 5, and there are exactly six ways of arranging these numbers: 345, 354, 435, 453, 534, 543. Similarly, if the number ends in 24, 32, or 52, the first three digits will be 135, 145, and 134 respectively.

As there are six ways of arranging three digits: abc, acb, bac, bca, cab, cba, there are 4×6 = 24 different 5-digit numbers that are divisible by 12.

The input will contain five lines of data. Each line will contain two whole numbers, D1 and D2. D1 will represent the number of unique digits (starting at 1), that will form the number. 3 ≤ D1 ≤ 9. D2 represents the divisor. 2 ≤ D2 ≤ 50.

For each input line, the output will contain the number of different D1-digit numbers that are divisible by D2.