PROBLEM LINK: CodeChef: Practical coding for everyone
DIFFICULTY: EASY
PREREQUISITE: Modular-Arithmetic
PROBLEM
There are N sweets that have to be distributed equally among M friends. You can remove K sweets from the N sweets and try to redistribute the sweets if needed. What is the minimum number of times you will have to remove K sweets such that the remaining sweets can be distributed equally among the M people?
EXPLANATION
We have N candies to distribute among M friends. Since we throw can throw K candies at a time, we can write -
N = a*M + c*K where a and c are positive integers
Let GCD (M, K) = g .
If N mod g != 0, output -1 since no solutions for the given equation then.
Otherwise, divide the whole equation by g to remove any common factors.
Then say n=N/g, m=M/g, k=K/g
n = a*m + c*k (m and k are coprime)
Take modulo m both sides
n % m = (c*k) % m
Since m and k are coprime, inverse modulo of k exists. Therefore, multiply by k^{-1} both sides of the equation.
(n * k^{-1})%m = c % m
This means c = p*m + ((n * k^{-1})%m) where p is a positive integer
For minimum value of c, p=0.
c = (n * k^{-1}) % m
(Remember that since m is not necessarily prime, but m and k are coprime, we use the coprime algorithm for finding inverse modulo of k).
A simple check is needed at the end to make sure that N-c*K is positive so that the remaining sweets are positive.