DivisiblePermutations | Topcoder Archive

Problem Statement

We define a permutation of an integer N as an integer that has the exact same digits as N, but possibly in a different order. Two permutations of N are considered different if the numbers they represent are not the same. For example, the set of all different permutations of the number N = 313 is {133, 313, 331}.

Given a String N and an int M, determine the number of different permutations of N that are divisible by M.

Definition

Class:: DivisiblePermutations
Method:: count
Parameters:: String, int
Returns:: long
Method signature:: long count(String N, int M)
(be sure your method is public)

Constraints

N will contain between 1 and 15 non-zero digits ('1'-'9'), inclusive.
M will be between 1 and 50, inclusive.

Examples

```
"133"
```
```
7
```
```
Returns: 1
```
There are three permutations of 133 (133, 313, 331), but only 133 is divisible by 7.
```
"2753"
```
```
5
```
```
Returns: 6
```
The permutations of 2753 that are divisible by 5 are 2375, 2735, 3275, 3725, 7235 and 7325.
```
"1112225"
```
```
5
```
```
Returns: 20
```
```
"123456789"
```
```
17
```
```
Returns: 21271
```
```
"987654321999999"
```
```
39
```
```
Returns: 19960896
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.