prob : https://www.hackerearth.com/problem/algorithm/magic-fractions/description/
I’ve read the editorial but didn’t understand why they are doing pow(2, t1). Can someone please elaborate that part.
I understood that we have to group the primes together to ensure gcd(a, b) = 1 but how to impose the constraint (a < b)?
See lets say for a given n,there are x primes,
so number of ways are obviously 2^x (like just see bitwise representation(0 means belong to numerator,1 ->dinominator))
So for imposing condition a<b,u can see that in any configuration eg: 0010110 ,either product of 0’s is more,or product of 1 is more,they are not equal.So basicaly according to which of the two are greater we can decide the numerator and dinominator according to that(like if product for all 0 is greater then we can put that 0’numbers to dinominator,and 1 to numerator)
So concluding: a and ~a should be counted 1 ,and not twice
i mean in 01010 and 10101 ,we know exactly one of them satisfies if we define 0’s to be numerator and 1’s to be dinominator
So ans is 2^(x-1) where x is number of primes<=N
thanks mate 