Factorial Fun!


Can anyone explain the approach of above problem pls?

First thing that as number of test cases are about 100000 So , you have to solve each test case in O[n].
obviously 1!!=0 and 2!!=1 and 3!!=1 and 4!!=1.
Initially even=1 and odd=1beacuse 2 and 3 are prime factors respectively.
You can store value of all N!! in an array of size 1000000 before test case loop.
For calculating N!! run loop from i=5 to i=1000000 and follow below steps :-

  1. If i is odd then (if i is prime then odd++ ) f[i]=odd.
  2. If i is even then (if i/2 is prime then even++ ) f[i]=even.
    You can view my solution here https://www.codechef.com/viewsolution/26877852

Hope it helps :wink: