Could not find the logic

#1

Could not find the working logic of this problem. Please help me.

#2

For a given integer x,
you need to find the number of pairs <a,b> such that gcd(a,b)=1.
So, you need to find the number of pairs <a, x!/a> such that a ϵ {factors of x!}.

OR

It follows a pattern. I can give you a hint.
The task is to factor n! into a and b such that gcd(p,q)=1 and p<q. so we calculate the number of distinct primes in n!
Let prime factorisation of n!= (p1)^x1 * (p2)^x2 …(pk)^xk
now for each i, (pi)^xi can either go in p or q. hence 2^k ways. but as we want p<q. therefore only 2^(k-1) ways.

Hope, this would help.
Check this code if you implementation issues, https://ide.codingblocks.com/s/269499

#3

but 2^(k-1) must give an even integer, but it in the sample test case it is giving a 3 which is odd

#4

2^(k-1) is odd for k=1.

#5

but how 2^(k+1) is 3. Moreover I could not get how to solve this question. Please help me

#6

fo(i,3,N)

{

    if(!sieve[i])

    {

        k*=2;

    }



    dp[i] = k;

}

k is simply the count of ways to choose unique factors in i!, now we ignore 2 as a factor, because we want 2^(uniquefactor-1), so we start with 3.
After that we just sum up.

If 3 unique factors, then we have 2^(3-1) = 4, so if you simulate until 5, k=4.