A correction, it is *(2^p) - 1 *, and the answer (*2^(number of primes less than n)) - 1* .(It is simply taking any subset of the primes,leaving the one in which do not take any prime)
On Sun, Jun 10, 2012 at 10:03 PM, Piyush Kapoor <[email protected]> wrote: > The problem simply asks you to calculate the number of ways to express a > number( = *N!^N!*) as product of two co prime numbers. > For a general *N* , it is simply equal to *2^(p-1)* , where *p * is the > number of distinct prime factors of *N*. > For *N!* , *p* will be number of primes less than *N* , and for *N!^N!* it > is same as *N!* , > So the answer is *2^((number of primes less than N) - 1)* . > > > On Sun, Jun 10, 2012 at 9:53 PM, payel roy <[email protected]> wrote: > > Can you please simplify the algorithm? Solution is not clear from the > posted > > submissions !!! > > > > > > On 10 June 2012 20:32, KK <[email protected]> wrote: > >> > >> This problem is of ACM-ICPC kanpur online round 2012. > >> you can find the solution here. > >> > >> > >> On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: > >>> > >>> Find the number of fractions a/b such that- > >>> > >>> 1. gcd(a, b) = 1 > >>> 2. 0 < a/b < 1 > >>> 3. a * b = (n!) ^ (n!) > >>> > >>> Where "n!" denotes the factorial of n and "^" denotes power, i.e. (2!) > ^ > >>> (2!) = 4. > >> > >> > >> On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: > >>> > >>> Find the number of fractions a/b such that- > >>> > >>> 1. gcd(a, b) = 1 > >>> 2. 0 < a/b < 1 > >>> 3. a * b = (n!) ^ (n!) > >>> > >>> Where "n!" denotes the factorial of n and "^" denotes power, i.e. (2!) > ^ > >>> (2!) = 4. > >> > >> -- > >> You received this message because you are subscribed to the Google > Groups > >> "Algorithm Geeks" group. > >> To view this discussion on the web visit > >> https://groups.google.com/d/msg/algogeeks/-/0tnSKnC7YRYJ. > >> > >> To post to this group, send email to [email protected]. > >> To unsubscribe from this group, send email to > >> [email protected]. > >> For more options, visit this group at > >> http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > > > -- > Regards, > Piyush Kapoor, > 2nd year,CSE > IT-BHU > -- *Regards,* *Piyush Kapoor,* *2nd year,CSE IT-BHU* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
