a/b mod p

-
ab^{-1} \pmod{p} = ab^{p-2}\pmod{p} (making use of Fermat's little theorem).

Comments

Post a Comment

Popular posts from this blog

ETF - Euler Totient Function

-
                                      ETF - Euler Totient Function SPOJ: - http://www.spoj.com/problems/ETF/ CodeChef :- Rational Numbers (it is sum of phi upto n) In number theory, Euler's totient function (or Euler's phi function), denoted as φ(n) or ϕ(n), is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n. (These integers are sometimes referred to as totatives of n.) This is very common in number theory the formula for finding the number of numbers less than and co-prime with n is N(1-1/p1)(1-1/p2).... where p1,p2.... refers to the distinct prime divisors of the number. A example always makes it clear ,lets take n=20 hence the prime divisors are 2,5 hence by formula the number of numbers less than and prime to 20 should be 20*(1-1/2)(1-1/2)=20(1/2)(4/5)=8 Now we can count also 1,3,7,9,11,14,17...
Read more

Minimum Steps to reach a destination (Recursive method )

-
http://www.geeksforgeeks.org/minimum-steps-to-reach-a-destination/ GeeksforGeeks. It is a ""branch and bound"" type of recursive problem, in which we have two options of going either left or Right in a number line.  And the target is to reach a particular point. Starting Point is Zero. #include<bits/stdc++.h> using namespace std; int fi(int dest,int steps,int cu) {  if(cu==dest)     return steps;  if(abs(cu)>dest)     return INT_MAX;   return min(fi(dest,steps+1,steps+cu+1),fi(dest,steps+1,cu-steps-1)); } int main() { int dest,i,j; cin>>dest; cout<<fi(dest,0,0)<<endl; return 0; }
Read more

Divide Intervals Into Minimum Number of Groups

-
  Divide Intervals Into Minimum Number of Groups  Leetcode Problem  Divide Intervals Into Minimum Number of Groups   is very much similar to the number-of-the-smallest-unoccupied-chair  Here we have to divide the given intervals into minimum number of groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other. Solution: We will think each interval as combination of two events ,  startTime  and endTime. 1) We create a list of events and then sort that list.  2) After that, we Initialise a min heap. which can be thinked like different baskets or groups.  3) We iterate through the events one by one, and assign each events to groups (picked from minheap).      While iterating starting event we pick a group from min heap and keep track in an array.       While iterating ending event through our tracking array, we release the group again in min...
Read more