FACTMUL problem in SPOJ

general
1

question link:- http://www.spoj.com/problems/FACTMUL/
link to my solution:- http://ideone.com/U97WEX
What’s wrong with my code?Pls someone help

2

hello raul1rnjn535_3
first of all i would like to mention if you are running your loop n times then there i no benefit of finding factors of the given mod. for each value of n >= 587117 answer is zero ok .
i myself was not able to get AC for this problem in CPP but when i submitted the same code in python it got accepted.
checkout both of these solution i think you will get what you are looking for… :smiley:

both code are exactly same.
http://ideone.com/gY14OD cpp code WA

http://ideone.com/VILk12 python code AC

1 Like
3

@ma5termind…even I knew the soln in Python but I wanted to solve it in C…I think there is an overflow after n=11.Since Python has a very large size of int overflow does not occur but that is not the case with C/C++…u may chek yrself…thanx anyways for yr reply…

4

yes you are right even i was astonished why same solution in cpp giving me wrong answer but there are some accepted solution in CPP. but no problem i will try it again then respond you :smiley:

5

@ma5termind can you please write the code how did you get no. 587117?

6

This is the AC answer in C++. You can easily convert it to C if you want.

http://ideone.com/UVyXq0

7

A bigger version of the same problem is also available on SPOJ
here it is :: it will amazed you.

8

@ma5termind is there a trick to get that 587117 as i found that number the hard way

9

@achut yes you can simply run a loop to sqrt(mod) to find the factors of mod value ":smiley:

10

The accepted solutions prompted me to try it in cpp/c…

11

hmm do comment here if you are able to get AC with the cpp code

12

to read about bit manipulation read from topcoder there is a tutorial over this topic

13

It is actually pretty easy.

Run a loop till sqrt(MOD). Find it’s biggest factor i.e 587117.

Thus any factorial of number >= 587117 will be 0 when done modulo the given number in the question.

1 Like