Hi, I read this Topic and I was thinking about its applications in contest but I couldn't get any.
I only know that this algorithm is useful for cryptography but I worder how it could be used in contests.
If you could provide me an example I would be grateful and a problem would be useful too.
Thanks in advance.
UPDATE: thanks to all, i continue reading and I found this link, it is another application.
For example that or that. Both of them are quite common sub-tasks.
Here are some problems on UVA online judge from uHunt
10104 — Euclid Problem
10090 — Marbles
10633 — Rare Easy Problem
10673 — Play with Floor and Ceil
It seems, like the third problem can be solved using simple math.
Try to solve Chinese remainder problem using extended Euclidean algorithm.
Could you explain anymore?
Does the explanation hzyfr did make sence or you need more clarification?
Yes, I need more information. :) Thank you.
Try to consider the problem of finding A mod N = n1*n2*...*nk given m1 = A mod n1, m2 = A mod n2, ..., mk = A mod nk.
You can do that via finding A mod n1*n2, A mod n1*n2*n3, A mod n1*n2*n3*n4, ..., A mod N.
It is sufficient to consider the case of two variables.
A = k1*n1 + m1 = k2*n2 + m2
k1*n1 — k2*n2 = m2 — m1
We can find k1 and k2 using Extended GCD.
You can find comprehensive article on CRT on wikipedia.
+1, What a surprising solution. :)
Extend-gcd will give you one solution to the equation ax+by=gcd(x,y). That is a very basic thing when you are trying to deal with linear modular equations and something related to that.
Chinese Remainder Theorem is also a useful tool in solving modular problems as NotImplemented mentioned. You can combine extend-gcd algorithm with CRT to get the result.