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 <smithpa...@gmail.com> wrote: > Can you please simplify the algorithm? Solution is not clear from the posted > submissions !!! > > > On 10 June 2012 20:32, KK <kunalkapadi...@gmail.com> 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
