question link http://www.codechef.com/DMNT2014/problems/MULFACT.
I got the concept(after the event ) but what I couldn’t understand was as to how coders get to conclusion that after n=999983 all numbers will have their superfactorial == 0(mod 329885391853)
A number N will be 0 (modulo M) only if N = k * M where k is some integer constant.There are 2 possibilities in this question :
M is a prime > all N : In this case there is no option but to calculate the answer by brute force. Pre-computation is also not feasible as n can be upto 10^9.Hence we look at the next possibbilty.
M is not a prime. In this case M = p * q. If you are write a simple brute force script like :
for i in range(3,1000000,2):
if(329885391853 % i == 0):
print 329885391853/i, i
break
This gives result as 999983 329891. Now for any number N greater than or equal to 999983, N! will have both 329891 and 999983 as factors i.e M will be a divisor of N! for all N>=999983. Hence the conclusion.