ICL1903 EDITORIAL

PROBLEM LINK: https://www.codechef.com/ICL2019/problems/ICL1903

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.

3 Likes