help needed in an interview question.

help_please
maths
number-theory
prime

#1

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)?


#2

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


#3

@vijju123 if possible can you please look into it?


#4

thanks mate :slight_smile: