Connection Status:
Competition Arena > Multifactorial

Multifactorial

SRM 335 · 2007-01-17 · by soul-net

SRM 335 · 2007-01-17 · by soul-net · Simple Math, Simple Search, Iteration
Class Name: Multifactorial
Return Type: String
Method Name: calcMultiFact
Arg Types: (int, int)
Problem Statement

Problem Statement

A multifactorial of a number is a generalization of the factorial function. The k-multifactorial of n is denoted by fack(n). The k-multifactorial of n is the product of every positive number of the form n - X*k, where X is a non-negative integer. For example, the 3-multifactorial of 14 is 14*11*8*5*2 = 12320, and the 4-multifactorial of 5 is 5*1 = 5.

A formal definition of multifactorial is:

  • fack(n) = n if k >= n
  • fack(n) = n*fack(n-k) if k < n

You will be given n and k and have to return the value of fack(n) as a String with no leading zeroes (this value is always a positive integer). If fack(n) is strictly greater than 1000000000000000000 (1018), return "overflow" (quotes for clarity) instead.

Notes

  • 1000000000000000000 (1018) fits in a long.

Constraints

  • n and k will each be between 1 and 2000000000 (2*109), inclusive.
Examples
0)
14
3
Returns: "12320"

The first example in the problem statement.

1)
5
4
Returns: "5"

The second example in the problem statement.

2)
1000
2
Returns: "overflow"

Way too big!

3)
2000000000
1900000000
Returns: "200000000000000000"
4)
1000
256
Returns: "84232704000"

Submissions are judged against all 175 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Multifactorial with a public method string calcMultiFact(int n, int k) · 175 test cases · 2 s / 256 MB per case

Submitting as anonymous