q-: https://www.hackerearth.com/problem/algorithm/magic-fractions/

anyone please explain me, how to solve this problem.

for every i from 1 to n, find the possible magic fractions for i.

To find possible magic fractions for a particular i :

You just need the no of primes upto i.

**why**:

If prime factorization for i! is (2^x * 3^y *…11^z) then:

possibilities for a and b can be (2^x-1 * 3^y-1… , 2 * 3 …) or (2^x * 3^y… , 11^z…).

it is clear that 1st possibility is not correct (as gcd wont be 1).

so we doesn’t care about prime powers, we care about no of primes.

so possibilities for a and b can be 2^(no of distinct primes in i!)/2 (selecting a and b from i!) and no of distinct primes in i! is nothing but no of primes upto i.