Problem Statement |
| | Many people know that a number is divisible by 3 if and only if the sum of its digits is divisible by 3, and similarly for divisibility by 9. Some know that a number is divisible by 6 if and only if the sum of the least significant digit (the ones place) and each of the other digits times four is divisible by 6, e.g., 792 is divisible by 6 and 4*7 + 4*9 + 1*2 = 66, which is divisible by 6. Of course, this is just in base 10. It turns out that for every number, in every base, there is a "divisibility rule".
Suppose you want to find a rule for dividing by some divisor in a certain numerationBase. Raising numerationBase to the i-th power and taking the result modulo divisor, you obtain a multiplier for the i-th digit of a number. For example, in base 10, dividing by 3, we get the multipliers:
- 100 % 3 = 1 % 3 = 1
- 101 % 3 = 10 % 3 = 1
- 102 % 3 = 100 % 3 = 1
- ...
so if the result is divisible by 3 when each digit is multiplied by 1, the original must have been divisible by 3 as well.
When the same multiplier is used for digit j as for digit i, with j > i, a cycle has been detected and will repeat for the remainder of the rule.
Since both 3 and 9 have the same rule in base 10, namely, "multiply each digit by 1, sum them, and check to see if the result is divisible by 3 (or 9, respectively)", you wonder whether other digits have similar divisibility rules. Determine the number of digits in numerationBase which have the same divisibility rules as divisor. A number is considered a digit in a numerationBase if it is between 0 and numerationBase - 1, inclusive, but we will exclude 0 and 1 from consideration. |
| |
Definition |
| | | Class: | DivisibilityRules | | Method: | similar | | Parameters: | int, int | | Returns: | int | | Method signature: | int similar(int numerationBase, int divisor) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Here the 0-th digit in a number is the least significant digit, and so on. |
| - | The multipliers in the divisibility rule for a divisor must be less than divisor. For example, though the rule "multiply every digit by 4, sum the results, and check for divisibility by 3" would work for numerationBase 10, divisor 3, we do not consider it valid since 4 >= 3. |
| - | The result should always be at least 1: divisor has the same divisibility rules as divisor! |
| |
Constraints |
| - | numerationBase will be between 3 and 1000, inclusive. |
| - | divisor will be between 2 and numerationBase-1, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 2 | | Both 3 and 9 have the same divisibility rules in base 10: multiply each digit by 1, sum the results, and check for divisibility by 3 or 9 respectively. |
|
|
| 1) | |
| | | Returns: 2 | | 2 and 5 have the same divisibility rules in base 10: add 1 times the 0-th digit and 0 times the other digits; see if the result is divisible by 2 or 5 respectively. |
|
|
| 2) | |
| | | Returns: 10 | | The identical rules are for digits 32, 40, 60, 80, 96, 120, 160, 240, and 480. Each has the following rule: Multiply the 0th, 2nd, 4th, 6th, etc. digits by 1, multiply the 1st, 3rd, 5th, etc. digits by 31, add the results, and check for divisibility by 32, 40, 60, 80, 96, 120, 160, 240, or 480. |
|
|
| 3) | |
| | |
| 4) | |
| | |
| 5) | |
| | |