×

# occurring 0 while calculating factorial mod 10^9 .

 0 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 ? This question is marked "community wiki". asked 25 Oct '15, 10:22 39●6 accept rate: 0%

 2 What are the constraints on n and m? answered 25 Oct '15, 10:57 5★saar2119 121●3 accept rate: 0% 1
 1 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. answered 25 Oct '15, 15:10 893●2●11●35 accept rate: 10% ohh yess.... I can't do this in case of a!/b! .. I apologize ... (25 Oct '15, 21:53)
 1 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. answered 25 Oct '15, 15:15 7★ceilks 1.8k●9 accept rate: 36%
 0 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 answered 25 Oct '15, 12:15 96●2 accept rate: 14% yes.. true .. fact[40] is completely divided by 10^9 . Thats the problem. I updated the question . It may now clear !!! (25 Oct '15, 14:36)
 0 u are dealing with a special case where in n! mod m , m is a non-prime there are different algos available for this http://stackoverflow.com/questions/14802566/calculating-n-mod-m-when-m-is-not-prime this might help answered 25 Oct '15, 14:11 2★aarush22 1 accept rate: 0% yess !! this is great . But I want to store (n! % 10^9) in advance so that I can use it in future . (25 Oct '15, 14:30)

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

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"; }

6★vsp4
1.2k138
accept rate: 28%

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

(25 Oct '15, 14:38)

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

(25 Oct '15, 14:49) 6★

yesss . . n>=m ..

(25 Oct '15, 15:49)
 0 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. answered 25 Oct '15, 15:15 7★ceilks 1.8k●9 accept rate: 36%
 0 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. answered 25 Oct '15, 21:47 4★abbas 411●8 accept rate: 28%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×348
×196
×31

question asked: 25 Oct '15, 10:22

question was seen: 1,905 times

last updated: 25 Oct '15, 21:53