TopCoder problem "DivisibilityCriteria" used in SRM 239 (Division II Level Three)



Problem Statement

    It is well known that a number is divisible by 2 if and only if its rightmost digit is divisible by 2. A number is divisible by 3 if and only if the sum of its digits is divisible by 3. Assessing divisibility by 7 is a bit more complicated: starting from the rightmost digit, we multiply the first digit by 1, the second by 3, the third by 2, the fourth by 6, the fifth by 4, the sixth by 5, the seventh by 1, the eighth by 3 and so on ... Then, we sum up these results. The number thus obtained is divisible by 7 if and only if the initial number was divisible by 7.



In this problem, you will be given an int N representing the number of digits the number has, and a prime number P. Your task is to find a divisibility criterion for a number with N digits with a prime P. More specifically, you should assign a factor for each digit, such that their sum is divisible by P if and only if the N-digit number is divisible by P.

In order to ensure the uniqueness of the solution, we add the following restrictions:

- all the factors must be between 0 and P-1 inclusive.

- the factor for the rightmost digit should be 1.

- if the N-digit number has leading zeros, the returned factors should still work.



Return a int[] representing the factors assigned to each digit, starting with the leftmost digit.



 

Definition

    
Class:DivisibilityCriteria
Method:multipliers
Parameters:int, int
Returns:int[]
Method signature:int[] multipliers(int N, int P)
(be sure your method is public)
    
 

Constraints

-P is a prime number less than 100.
-N is between 1 and 18, inclusive.
 

Examples

0)
    
6
7
Returns: {5, 4, 6, 2, 3, 1 }
We know that the rightmost digit should be multiplied by a factor of 1. Now we want to find the factor for the next digit. Let's consider the number 35, which is divisible by 7. The factor for digit '3' can now be found from the following formula: 3 * x + 5 * 1 mod 7 = 0, where x is between 0 and 6 (see the problem statement). This leads us to the unique solution, x=3. To find the next factor, we take a three digit number which is divisible by 7, let's say 532. If we denote by y the factor of '5', we should have: 5 * y + 3 * 3 + 2 * 1 mod 7 = 0. This leads us to the unique solution, y=2. Proceeding analogously for the next digits of the number, we obtain successively the factors 6, 4 and 5.
1)
    
7
11
Returns: {1, 10, 1, 10, 1, 10, 1 }
2)
    
5
13
Returns: {3, 12, 9, 10, 1 }
3)
    
2
2
Returns: {0, 1 }
Note that only the rightmost digit counts when assessing the divisibility with 2, so if the number has more than one digit, all the other factors are 0.
4)
    
16
97
Returns: {45, 53, 15, 50, 5, 49, 34, 81, 76, 27, 90, 9, 30, 3, 10, 1 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4481

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6538&pm=4481

Writer:

supernova

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Math, Simulation