10407 - Simple division

[lighted]

I see that you already got accepted.

[richatibrewal]

Yes, by the method of gcd. But i couldn't understand the test case. Will someone plz throw some light on the 3rd test case??

[lighted]

14%3 = 2
whereas -22%3 = 1

There is mistake in mod calculation. (-22) % 3 = (-21) % 3 + (-1) % 3 = 0 + (-1 + 3) % 3 = 2.

Or (-22) % 3 = (-22 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) % 3 = 2.

[richatibrewal]

Thanx

[zodiacLeo]

Hello guys,

I've got "10407 - Simple Division" AC using the description in Algorithmist. However, I don't fully understand it.

My algorithm:
- Add numbers to set "S".
- If size of S is two: print the difference between the two numbers.
- If size of S is > 2: Erase the first element, and find GCD among all the differences between the remaining numbers.

This works correctly. But can anybody explain it in simple words? How can I figure out that the largest dividend with same remainder among a set of numbers is the GCD among the differences except the first difference?

Thanks in advance.

Let there be 3 (replace "3" with "n" after I complete the explanation) numbers, n1, n2, n3.
The problem claims that there exists a number, "x" which given same remainder, "r" when you divide each of the three numbers with x.
I know for a fact that, if one removes the remainder from a dividend, then the number so obtained becomes completely divisible by divisor( "x" in this case) (which I still have to find). Taking this further, if I subtract "r" from each number like - "n1-r", "n2-r", and "n3-r", then these numbers would be divisible by x.

So we have a number "x" which divides 3 numbers (GCD is screaming!!!). Yes!! x = GCD( n1-r, n2-r, n3-r) is your answer. So if you generate "r" iteratively (like r = 0, 1, 2, ...) and subtract it from each number and then find the GCD then, BAM!! You have your answer!
(The above solution is likely to TLE, but it is important to understand the "improved" solution)

Let's try to improve this further -
My goal is to reduce each number in the list to a values that give me remainder 0. More precisely, I want to convert ->
n1 -> n1-r
n2 -> n2-r and
n3 -> n3-r. But in just one step!. How? How?

If I make the first number (n1) as 0, and subtract n1 from each of the other number then I have something like this -
n1 = 0
n2 = n2 - n1
n3 = n3 - n1

If I choose any number as a divisor and n1 as the dividend, then the remainder is always going to be zero. So in order to find a number that divides n2, and n3 completely, I need to find the GCD(n2, n3).