thanks Renato i got it ,,.... On 27 Feb, 17:20, Renato Parente <[email protected]> wrote: > a/b % mod = a* (b^-1) % mod > Since mod = 10^9 + 7 is a prime, so it's 'cheap' to find (b^-1) % mod > instead of checking every possible value. > One of the ways it's noticing that, for any b,n such that n is a prime and > b is not divisble by n, b^(n-1) = 1 (mod n). If you notice, b^(n-1) = > b*b^(n-2), therefore, b^(n-2) is the modular inverse of b, that's why the > formula is like that > > I hope you've understood :) > > On 27 February 2012 09:13, Mitesh Joshi <[email protected]> wrote: > > > > > > > > > problem find a/b modulo 10^9+7 .... > > mod=10^9+7 > > bcoz a and b some value which more than mod... > > > so the solution uses a/b= ( (a%mod) * ( (b%mod) ^ mod-2 ) ) % mod > > why..... > > > -- > > You received this message because you are subscribed to the Google Groups > > "Google Code Jam" 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/google-code?hl=en.
-- You received this message because you are subscribed to the Google Groups "Google Code Jam" 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/google-code?hl=en.
