occurring 0 while calculating factorial mod 10^9 .

general
, ,
1

I was calculating (n!/m!) mod 10^9 (not 10^9+7) . So I used following code to pre-calculate all factorials as:

fact[0]=1;

for(i=1;i<=n;i++)
{

fact[i] = (fact[i-1]*i)%mod; //mod = 10^9

}

1<=m<=n<=1000

But somewhere in between it introduced 0 and that 0 propagates till n . So how to overcome such situation ?And yes it is working fine if mod = 10^9+7 .

Sorry for bad language .

In above code I am storing factorial of any n<=1000. And final result will be calculated directly by

ans = (fact[n]/fact[m]) % mod .

But my fact array working fine till fact[39] .

i.e

fact[1]=1

fact[2]=2

fact[3]=6

fact[4]=24

fact[5]=120

fact[6]=720

.

.

fact[39]=800000000

fact[40]=0 //because (fact[39]*40) % 10^9 = 0

and therefore fact[41]=fact[42]= … fact[1000]=0 .

So how to overcome such situation ?

2

What are the constraints on n and m?

1 Like
3

1<m<=n<=1000

4

ur question is bit unclear if u can provide the complete code maybe i can help
but from what i think
if fact[i]is divisible by mod
than fact[i]%mod=0

5

u are dealing with a special case where in n! mod m , m is a non-prime there are different algos available for this

this might help

6

yess !! this is great . But I want to store (n! % 10^9) in advance so that I can use it in future .

7

I just ran your code, its working fine with no zero propogating. Whats the problem ? :expressionless:

long long int fact[1005];
int n = 1000;
#define mod 1000000007;

fact[0]=1;

for(int i=1;i<=n;i++) {

fact[i] = (fact[i-1]*i)%mod; //mod = 10^9

}

for(int i=1;i<=n;i++) {
cout << fact[i] << “\n”;
}

8

yes… true … fact[40] is completely divided by 10^9 . Thats the problem. I updated the question . It may now clear !!!

9

Yess It is working fine with mod 1000000007 . But in case of mod 1000000000 it is not !!!

10

Ooh okay. Is it always given that n >= m? or anything like that

11

Can you explain your problem? 10^9+7 is a prime number. So upto (10^9+6)! There will be no term which will be divisible by 10^9+7. But for 10^9 which is not a prime number, it’s prime factors will be covered by a sufficiently large n! which is 40 in this case. So you are getting zero after modulo.

Also, (a+b)%m = a%m + b%m. This is not the case for a/b. i.e.

a/b%m != a%m / b%m.

So your approach is wrong. You need modular inverse.

I am not sure how to find modular inverse for non-prime modulo. Sorry about that.

1 Like
12

Your “problem” actually leads to a quite efficient way. n!/m! will always be 0 if n-m>=40. So in any case you can compute n!/m! in at most 39 steps. This will be fast enough for at least roughly 10^6 testcases. If you have more you can in fact precompute the value for all 1<=m<=n<=1000.

1 Like
13

Your “problem” actually leads to a quite efficient way. n!/m! will always be 0 if n-m>=40. So in any case you can compute n!/m! in at most 39 steps. This will be fast enough for at least roughly 10^6 testcases. If you have more you can in fact precompute the value for all 1<=m<=n<=1000.

14

yesss . . n>=m …

15

if your modulo = 10^9 means you are just interested in the last 9 digits of your solution.

So if n!/m! has more than 9 zeros, your ans will be 0.

Now no. of zeros in n! is sum of multiples of power of 5

(since 5 * 2 = 10,25 * 4 = 100,etc and there are more mutliples of 2 than 5)

Roughly 40 consecutive terms lead to 9 zeros.

So you can precompute all values for n!/(x)! where x >= m and x >= n- 40

For other values , your ans is 0.

16

ohh yess… I can’t do this in case of a!/b! … I apologize …