In Dementia2014/Mulfact how does one arrive at conclusion that that superfactorial(n)%329885391853=0 for all n>=999983

general
,
1

question link CodeChef: Practical coding for everyone.
I got the concept(after the event :frowning: ) 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)

Thanks in advance

2

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 :

  1. 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.

  2. 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.

2 Likes
3

I realized it today when I saw that crazy looking MOD instead of 10^9 + 7 :slight_smile:

1 Like