Advertisements

How can I find `(n!) % m`

**faster** than `O(n)`

?

1 <= n <= 10^18,

1 <= m <= 10^6

### >Solution :

You can easily have `O(m)`

time complexity in the worst case (when `m`

is a *prime*) and it seems to be good enough since you have `m <= 1e6`

(while `n`

can be up to `1e18`

). Note, that when `n >= m`

```
n! = 1 * 2 * ... * m * ... * n
^
factorial is divisible by m
```

and that’s why

```
n! % m == 0 # whenever n >= m
```

Another *implementation* detail is that you don’t have to compute `n! % m`

as `1 * 2 * ... * n % m`

but you can do it as `((..(1 % m) * 2 % m) ... * n % m)`

in order not to deal with huge numbers.

**C#** code example

```
private static int Compute(long n, long m) {
if (n >= m)
return 0;
long result = 1;
// result != 0 - we can well get 0 and stop looping when m is not prime
for (long d = 2; d <= n && result != 0; ++d)
result = (result * d) % m;
return result;
}
```