You are not logged in. Please login at www.codechef.com to post your questions!

×

occurring 0 while calculating factorial mod 10^9 .

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

rajan_parmar's gravatar image

5★rajan_parmar
396
accept rate: 0%

edited 25 Oct '15, 14:39


What are the constraints on n and m?

link

answered 25 Oct '15, 10:57

saar2119's gravatar image

5★saar2119
1213
accept rate: 0%

1<m<=n<=1000

(25 Oct '15, 11:01) rajan_parmar5★

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.

link

answered 25 Oct '15, 15:10

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

ohh yess.... I can't do this in case of a!/b! .. I apologize ...

(25 Oct '15, 21:53) rajan_parmar5★

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.

link

answered 25 Oct '15, 15:15

ceilks's gravatar image

7★ceilks
1.8k9
accept rate: 36%

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

link

answered 25 Oct '15, 12:15

neerajjha_1994's gravatar image

1★neerajjha_1994
962
accept rate: 14%

edited 25 Oct '15, 12:16

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) rajan_parmar5★

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

link

answered 25 Oct '15, 14:11

aarush22's gravatar image

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) rajan_parmar5★

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

link

answered 25 Oct '15, 14:35

vsp4's gravatar image

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) rajan_parmar5★

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

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

yesss . . n>=m ..

(25 Oct '15, 15:49) rajan_parmar5★

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.

link

answered 25 Oct '15, 15:15

ceilks's gravatar image

7★ceilks
1.8k9
accept rate: 36%

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.

link

answered 25 Oct '15, 21:47

abbas's gravatar image

4★abbas
4118
accept rate: 28%

edited 25 Oct '15, 21:48

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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