Statistics

Problem Statement for "MegaFactorial"

Problem Statement

The factorial of the k-th order of a number n is denoted n!k and defined by the following recurrences:
1) n!k = n!(k-1) * (n-1)!k for n > 0 and k > 0
2) n!k = 1 for n = 0
3) n!k = n for k = 0

For example, 7!1 = 7! (the traditional factorial), and 5!3 = 5!2 * 4!3 = (5!1 * 4!2) * 4!3.

You are given ints N, K and B. Count the number of trailing zeros in the number N!K when it is written in base B and return it modulo 1,000,000,009.

Definition

Class:
MegaFactorial
Method:
countTrailingZeros
Parameters:
int, int, int
Returns:
int
Method signature:
int countTrailingZeros(int N, int K, int B)
(be sure your method is public)

Constraints

  • N will be between 1 and 1,000,000,000 (10^9), inclusive.
  • K will be between 1 and 16, inclusive.
  • B will be between 2 and 10, inclusive.

Examples

  1. 6

    1

    4

    Returns: 2

    6!1 = 6! = 23100 in base 4.

  2. 4

    2

    6

    Returns: 2

    4!2 = 4!1 * 3!2 = ... = 4! * 3! * 2! = 1200 in base 6.

  3. 10

    3

    10

    Returns: 22

  4. 50

    10

    8

    Returns: 806813906

  5. 1000000000

    16

    2

    Returns: 633700413

  6. 999999473

    15

    2

    Returns: 500955045

  7. 999997425

    15

    2

    Returns: 140202729

  8. 999948273

    15

    8

    Returns: 775102793

  9. 999999999

    16

    4

    Returns: 456164482

  10. 999997424

    16

    8

    Returns: 150210979

  11. 999948272

    16

    8

    Returns: 915138266

  12. 999999909

    16

    9

    Returns: 75432839

  13. 999931317

    16

    3

    Returns: 156213761

  14. 599998448

    16

    2

    Returns: 578863480

  15. 599982064

    16

    4

    Returns: 134266524

  16. 599785456

    16

    2

    Returns: 12733096

  17. 511180784

    16

    8

    Returns: 345838416

  18. 510656496

    16

    4

    Returns: 453356111

  19. 999030766

    14

    2

    Returns: 321827337

  20. 999030770

    14

    8

    Returns: 104162169

  21. 1

    1

    3

    Returns: 0

  22. 1

    15

    4

    Returns: 0

  23. 2

    16

    2

    Returns: 1

  24. 3

    16

    2

    Returns: 16

  25. 151

    14

    2

    Returns: 548165411

  26. 512378

    9

    5

    Returns: 884264929

  27. 88

    8

    8

    Returns: 203347860

  28. 127

    11

    3

    Returns: 734179084

  29. 188425

    4

    6

    Returns: 190877618

  30. 996299288

    13

    3

    Returns: 16838156

  31. 921750

    10

    7

    Returns: 344538785

  32. 1000000000

    10

    9

    Returns: 534473941

  33. 999982959

    12

    10

    Returns: 137773246

  34. 3000

    6

    7

    Returns: 174383541

  35. 123424

    5

    7

    Returns: 729306708

  36. 125125124

    12

    5

    Returns: 653798224

  37. 100000999

    7

    8

    Returns: 67391348

  38. 999858252

    13

    9

    Returns: 133092654

  39. 514928839

    16

    9

    Returns: 745852448

  40. 1000

    1

    4

    Returns: 497

  41. 1000000

    1

    3

    Returns: 499993

  42. 25000000

    1

    10

    Returns: 6249998

  43. 999666888

    1

    9

    Returns: 249916718

  44. 1000000000

    1

    7

    Returns: 166666661

  45. 990117872

    16

    5

    Returns: 938595737

  46. 990380016

    16

    4

    Returns: 748471515

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: