Statistics

Problem Statement for "DivisibilityRules"

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

  1. 10

    3

    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.

  2. 10

    5

    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.

  3. 511

    32

    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.

  4. 3

    2

    Returns: 1

  5. 1000

    999

    Returns: 7

  6. 528

    382

    Returns: 1

  7. 541

    289

    Returns: 1

  8. 319

    190

    Returns: 1

  9. 21

    18

    Returns: 1

  10. 384

    210

    Returns: 1

  11. 957

    556

    Returns: 1

  12. 424

    223

    Returns: 1

  13. 164

    137

    Returns: 1

  14. 169

    69

    Returns: 1

  15. 333

    86

    Returns: 1

  16. 65

    46

    Returns: 1

  17. 274

    190

    Returns: 1

  18. 424

    248

    Returns: 1

  19. 692

    29

    Returns: 1

  20. 45

    44

    Returns: 5

  21. 348

    37

    Returns: 1

  22. 566

    218

    Returns: 1

  23. 659

    528

    Returns: 1

  24. 523

    323

    Returns: 1

  25. 174

    13

    Returns: 1

  26. 97

    96

    Returns: 11

  27. 403

    119

    Returns: 1

  28. 119

    17

    Returns: 2

  29. 655

    532

    Returns: 1

  30. 716

    246

    Returns: 1

  31. 425

    203

    Returns: 1

  32. 333

    166

    Returns: 5

  33. 804

    373

    Returns: 1

  34. 531

    193

    Returns: 1

  35. 164

    60

    Returns: 1

  36. 14

    3

    Returns: 1

  37. 14

    4

    Returns: 1

  38. 14

    3

    Returns: 1

  39. 14

    4

    Returns: 1

  40. 15

    4

    Returns: 1

  41. 15

    6

    Returns: 1

  42. 21

    6

    Returns: 1

  43. 21

    9

    Returns: 1

  44. 26

    3

    Returns: 1

  45. 26

    4

    Returns: 1

  46. 26

    6

    Returns: 1

  47. 26

    8

    Returns: 1

  48. 1000

    11

    Returns: 3

  49. 1000

    15

    Returns: 5

  50. 1000

    18

    Returns: 5

  51. 1000

    19

    Returns: 1

  52. 1000

    22

    Returns: 1

  53. 1000

    26

    Returns: 1

  54. 1000

    28

    Returns: 1

  55. 1000

    30

    Returns: 5

  56. 1000

    31

    Returns: 1

  57. 1000

    32

    Returns: 2

  58. 998

    45

    Returns: 1

  59. 998

    46

    Returns: 1

  60. 998

    48

    Returns: 1

  61. 998

    49

    Returns: 1

  62. 998

    54

    Returns: 1

  63. 996

    28

    Returns: 1

  64. 996

    30

    Returns: 3

  65. 996

    31

    Returns: 1

  66. 996

    48

    Returns: 1

  67. 996

    49

    Returns: 1

  68. 996

    51

    Returns: 1

  69. 1000

    500

    Returns: 14

  70. 499

    100

    Returns: 2

  71. 1000

    333

    Returns: 7

  72. 1000

    667

    Returns: 1

  73. 1000

    666

    Returns: 1

  74. 999

    333

    Returns: 6

  75. 999

    221

    Returns: 1

  76. 998

    100

    Returns: 1

  77. 999

    998

    Returns: 3

  78. 965

    934

    Returns: 1

  79. 999

    99

    Returns: 1

  80. 720

    2

    Returns: 28

  81. 344

    56

    Returns: 3

  82. 15

    4

    Returns: 1

  83. 89

    86

    Returns: 1

  84. 366

    270

    Returns: 1

  85. 1000

    6

    Returns: 2

  86. 655

    532

    Returns: 1

  87. 20

    9

    Returns: 1

  88. 997

    12

    Returns: 11

  89. 398

    296

    Returns: 1

  90. 39

    12

    Returns: 1

  91. 900

    400

    Returns: 2

  92. 185

    88

    Returns: 1

  93. 258

    32

    Returns: 1

  94. 999

    4

    Returns: 1

  95. 7

    3

    Returns: 3

  96. 999

    992

    Returns: 1

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.
This problem was used for: