Internet Problem Solving Contest

IPSC 2006

Solution to Problem A – Another Candies

This problem is very simple. The only thing to do is to find out whether the sum of the candies is divisible by N. The simplest way to solve this problem is to sum the counts of candies. If the result is divisible by N, the answer is "YES", and if it is not, the answer is "NO". This works for the easy data set, but for the hard you may run into trouble with large numbers.

If we look at the hard input data, we can see that there are numbers up to 263. What we can improve in our solution is to work all the time only modulo N, and use the identity (A+B) mod N = ( (A mod N) + (B mod N) ) mod N. We compute the sum modulo N, and if the solution is zero, the answer is "YES", and in the other case, the answer is "NO".