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.
